A Markov Decision Process (MDP) is defined by:
A set of states \(S\). For pacman this could be grid positions.
A set of actions \(A\). For pacman, this would be North, South, East, and West.
A transition function \(P(s' \mid s, a)\) which represents the probability of being in state \(s'\) after taking action \(a\) from state \(s\).
A reward function \(R(s, a, s')\) which represents the reward received from being in state \(s\), taking action \(a\), and ending up in state \(s'\).
A start state \(s_0\in S\)
Potentially one or more terminal states
The Markov property says that given the present state, the previous and future states are all conditionally independent.
In the
context of MDPs, this means that actions depend only on the current state. That is to say, the following two
expressions are equivalent for MDPs:
\(P(S_{t+1}=s_{t+1}|A_t=a_t, s_t=s_t,
A_{t-1}=a_{t-1}, S_{t-1}=s_{t-1}...A_0=a_0,
S_0=s_0)\)
\(P(S_{t+1}=s_{t+1}|A_t=a_t, s_t=s_t)\)
A policy, \(\pi\), represents our plan. More formally, \(\pi\) is a function that maps states to actions (\(\pi: S
\rightarrow A\)). For each state \(s\in S\), \(\pi(s)\) will return the corresponding action from our plan.
An optimal policy is one that would maximize our expected utility if followed.
Exercise: How is this different than what expectimax does (hint: does expectimax tell you what to do for every state)?
The idea of discounting stems from the common idea that a reward now is better than the same reward later on. Therefore, according to this philosophy, we want to weight each value of a state by some factor \(\gamma \in [0, 1]\). If we do not restrict \(\gamma\) to this range, the game could last forever with the reward being infinite.
More concretely, the reward is worth \(\gamma^0*R\) now, and \(\gamma^1*R\) after one step and \(\gamma^2R\) after two, and so on. This is to ensure that we prioritize rewards now rather than later on in our path to the goal. A \(\gamma\) closer to 0 will mean that we have a smaller horizon and care more about immediate rewards and actions while a \(\gamma\) closer to 1 will weigh later rewards almost equally to immediate rewards.