Markov Decision Processes (MDP)

A row of four states, the last one a goal. Move left or right — each move costs $-1$, except the one that lands you on the goal, which pays $+10$. Unlike the bandit, your position now depends on every choice you've made so far, and every future choice depends on where those moves left you.

A Markov decision process is the tuple $(S, A, P, R, \gamma)$ — states, actions, a transition rule, a reward function, and a discount factor. For a fixed policy $\pi$, the value of a state is its expected discounted future reward, defined recursively by the Bellman equation:

• $V^\pi(s)$ — the value of state $s$ under policy $\pi$: its expected discounted future reward.
• $s$ — the current state, one of the situations the agent can be in.
• $\pi(s)$ — the policy: which action it prescribes from state $s$.
• $R(s, \pi(s))$ — the reward function: the immediate reward for taking that action in that state.
• $\gamma$ — the discount factor, shrinking the value of reward that takes longer to arrive.
• $P(s,\pi(s))$ — the transition rule: the state landed in after taking that action.

1. The same idea as the chain rule

   This is the exact same idea as Part I's chain rule — the value of right now depends on the value of whatever comes next — just unrolled over an action-dependent sequence of states instead of a fixed chain of functions.

Every state's value is highest closest to the goal and lower further away — not because those states are inherently better, but because $\gamma < 1$ discounts reward that takes longer to arrive. The value function is entirely a consequence of the policy and the discount, not something separately assigned to each state.

With $\gamma = 0.9$, under the policy "always move right":

1. Start from the goal and work backward

   $V(3) = 0$ (nothing left to earn). $V(2) = 10 + 0.9(0) = 10$ — one move from $+10$.

2. Two states from the goal

   $V(1) = -1 + 0.9(10) = 8$. $V(0) = -1 + 0.9(8) = 6.2$.

3. A policy that never arrives

   Under "always move left," any state above $0$ eventually gets stuck bouncing at the boundary forever, each bounce costing $-1$. Solving $V = -1 + 0.9V$ for a fixed point: subtract $0.9V$ from both sides to get $V - 0.9V = -1$, i.e. $0.1V = -1$, so $V = -1/0.1 = -1/(1-0.9) = -10$ — a genuinely worse value than even the very first state gets under "always right."