Markov Decision Processes So, how do we define an MDP or a Markov decision process? There's a set of states—we've seen that before—set of actions—we've seen that before. Now, to model the stochasticity, we have a transition model T(si, s') . What this is encoding is the probability if you start in state s, took action a, to then land in state s'. So, another way to write this is to write this as: this is really the same thing: P(s' | s, a) is the same as the probability of landing in state s' given that the previous time you were in state s and took action a. That's how we encode the stochasticity. Then, now instead of having just a utility at the very end of the game, we have rewards at every step. And this reward can depend on everything related to that step: the state you were in before, the action you took, and the state you land in. Then, sometimes you can simplify this, so you'll see some treatments where they'd say the reward just depends on s, just depends on s', or just on s_n, a. Those are just special cases where the reward function is simplified. You have a start state very often, and maybe you have terminal states, but we'll see that it's also possible to work within the MDPs where there are no terminal states, and your thing keeps running forever. So, these are non-deterministic search problems. We actually know how to solve these, but not in the efficient way that we're going to look at today. And so, we'll have a new tool very soon to solve this way. So, what is Markov about this? Markov decision processes, in general, whenever in artificial intelligence and even beyond, you see the word "Markov," it refers to this guy over here. But really, what it means technically is that you somehow have a sequence of things and you associate indices with these, corresponding to time, for example, and that whatever happened in the past is independent of what's going to happen in the future if you know what the state is at the current time. So, you have a separation: when you know the state at the current time, history won't affect anymore how things will be in the future. What that means is very similar to search, where once you know which state you're in, you don't need to look at where you came from to know where you would land next if you call your successor function. Same thing here: the transition model only depends on the current state and current action, not on past states and past actions. In full generality, you could have this: the next state depends on all past states and actions. But if you have the Markov assumption in place, then this simplifies to this expression over here. Okay, that's just an assumption. If that assumption is not true, and you say, "Oh, I have this state space, and actually the next state doesn't just depend on the current state and action but also on the previous state and previous action," there's actually a very simple fix. The simple fix is that you redefine your state space. Say my old definition of the state space wasn't really right because it didn't make it Markov, so I'm going to include the past state and the past action into my new, bigger state. And now, in this bigger state space, you're able to model it as a Markov decision process. Now, the catch, of course, is that you want to keep your state space and action space small, so you prefer to put as little as possible in your state while still having this Markov property. Okay, what's the goal in this whole MDP framework? The goal is to find a policy. This is different from what we've done before. Before, let's say in search, a start search, what you get back is a sequence of actions, but here, since we don't know the outcome of our actions, we cannot just restrict ourselves to computing a sequence of actions. We need to know, for every possible future state that we might visit, what the right action would be if we ever prescribe that action. A policy is something that prescribes for every state what action we should take. That's a policy. Anything that prescribes actions for every state is a policy. This will be one, or sometimes a few, policies that are optimal in the sense that they maximize the expected reward you will accumulate, and that's the policy we will be after: the one that maximizes the expected sum of rewards. So, what is the policy formally? It's a function from states to actions, and in essence, it defines what we know from the very beginning as a reflex agent. So, once we are solving an MDP and we're done solving it, what we get out is a policy. If we just store that policy, we now have a reflex agent, and we don't need to remember anything else. That reflex agent will actually be rational and do the optimal thing.