The reinforcement learning problem defined in Lecture 1 is held by the Markov decision process (MDP). Almost every reinforcement learning problem can be formalized as an MDP. Starting from the Markov chain, we add reward and then action, building it up one layer at a time. Silver carries a single example, the ‘student’, throughout the lecture, and we follow the same one.
Lecture slides: PDF
The Markov Property and Markov Processes
A state is Markov when the present state alone is enough to determine the future (Lecture 1). Knowing the entire past yields no better prediction than the present.
$$\mathbb{P}[S_{t+1} \mid S_t] = \mathbb{P}[S_{t+1} \mid S_1, \dots, S_t]$$Collecting the probabilities of moving between states gives the transition matrix $\mathcal{P}$, where $\mathcal{P}_{ss'} = \mathbb{P}[S_{t+1}=s' \mid S_t=s]$. A memoryless random process made up only of a state set $\mathcal{S}$ and this $\mathcal{P}$ is a Markov process (Markov chain).
Here Silver’s student example enters. The states are Class 1, Class 2, Class 3, Pass, Pub, Facebook, and Sleep. The student moves between these states probabilistically. Mid-class they slip into Facebook; on the verge of passing they stop by the pub and drift back to an earlier class. The probabilities of these moves are the transition matrix, and ‘Sleep’ is a terminal state: once you enter, you never leave.
The student Markov chain. Press “▶ Sample episode” to start at Class 1, step randomly through the states following the transition probabilities, and end at ‘Sleep’. Every run gives a different path.
Markov Reward Process (MRP)
Add reward and a discount factor to a Markov process and you get an MRP. Each state is assigned a reward $\mathcal{R}_s = \mathbb{E}[R_{t+1} \mid S_t=s]$, and a discount factor $\gamma \in [0,1]$ is set. In the student example, class is hard so it gives a negative reward, the pub is briefly enjoyable so it gives a small positive reward, and passing gives a large positive reward.
The return is the discounted sum of rewards from now on.
$$G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$When $\gamma$ is near 0 it is myopic, taking only the reward in front of it; near 1 it looks far into the future. There are several reasons to discount. It makes an infinitely continuing sum converge, it reflects the uncertainty of the far future, and it keeps the mathematics clean.
The value function is the expectation of the return, that is, the average of the rewards to be received going forward when starting from that state.
$$v(s) = \mathbb{E}[G_t \mid S_t = s]$$Splitting this into one step and the value of the next state is the Bellman equation.
$$v(s) = \mathcal{R}_s + \gamma \sum_{s'} \mathcal{P}_{ss'}\, v(s')$$It is the reward received now plus the values of the reachable next states, weighted by their probabilities. There is no maximum here. So it is a linear equation, and it can be solved by hand. Writing all the states at once as a vector gives this.
$$v = \mathcal{R} + \gamma \mathcal{P} v$$Gathering $v$ on one side gives
$$(I - \gamma \mathcal{P})\,v = \mathcal{R}$$and multiplying by the inverse solves it in one shot.
$$v = (I - \gamma \mathcal{P})^{-1}\mathcal{R}$$However, the inverse computation is $O(n^3)$ in the number of states $n$, so this direct solution is only usable for MRPs with few states. Large MRPs are solved with the iterative methods we will see later (dynamic programming, Monte Carlo, TD). And once the maximum enters in the MDP later, this linear solution breaks down and iterative methods become indispensable.
The same chain, now with a reward attached to each state. By sampling episodes while varying the discount factor γ, you can see how the return G changes even along the same path. The smaller γ is, the more it reflects only the reward in front; the larger, the further into the future.
Markov Decision Process (MDP)
Add action to an MRP and you get an MDP. Now the state no longer flows on its own; at each state the agent chooses an action, and that choice changes the transition and the reward. In the student example, the student decides whether to slip into Facebook or attend class, whether to go to the pub or study.
The rule for choosing an action is the policy $\pi(a \mid s) = \mathbb{P}[A_t = a \mid S_t = s]$. Fix a policy and two values can be measured. The state-value $v_\pi(s)$ is the expected return when following policy $\pi$ from that state, and the action-value $q_\pi(s,a)$ is the expected return when taking action $a$ in that state and then following the policy.
The two are defined through each other, and this is the Bellman expectation equation.
$$v_\pi(s) = \sum_a \pi(a\mid s)\, q_\pi(s,a), \qquad q_\pi(s,a) = \mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_\pi(s')$$The backup diagram Silver uses to explain the Bellman equation. The bright, large circles are states and the black dots are actions. It renders the equation above as a picture: the value $v_\pi(s)$ of state $s$ is the average of the action-values $q_\pi(s,a)$ after choosing each action under policy $\pi$, and the action-value is the value obtained by receiving reward $r$ and tracing back the values $v_\pi(s')$ of the next states reached following the transition probabilities $\mathcal{P}$. It draws the flow of value being backed up from the bottom to the top.
Now you choose an action directly at each state. Starting at Class 1, press either ‘Study’ or ‘Facebook’ and you receive that action’s reward and move to the next state. ‘Pub’ is probabilistic in its outcome, so there is no telling where it will bounce. A policy is, in the end, the rule for which button to press at each state.
Optimal Value and the Bellman Optimality Equation
What we want is not just any policy but the best policy. The optimal state-value $v_*(s) = \max_\pi v_\pi(s)$ and the optimal action-value $q_*(s,a) = \max_\pi q_\pi(s,a)$ are the best values that can be reached.
If you know $q_*$, the optimal policy comes for free. At each state, deterministically choose the action with the largest $q_*(s,a)$. Every MDP has at least one such deterministic optimal policy.
Put the maximum in place of the expectation and you get the Bellman optimality equation.
$$v_*(s) = \max_a \left( \mathcal{R}_s^a + \gamma \sum_{s'}\mathcal{P}_{ss'}^a\, v_*(s') \right)$$Because of the $\max$ it is nonlinear, so it does not solve in one shot like the earlier MRP. It needs iterative methods, and that is the dynamic programming of the next lecture.
Extensions
Silver notes some extensions at the end: infinite and continuous states, partial observability (POMDP), average reward without discounting. The skeleton is the same; it just becomes a little more delicate to handle.
In the next lecture we assume the MDP is fully known and enter dynamic programming, solving these Bellman equations by iteration to find the optimal policy.