Chapter 3 — finite Markov decision processes.

Chapter 3 is the theoretical heart of the book. It formalizes the full RL problem as a finite Markov decision process: the agent–environment interface, the dynamics function \(p(s',r\mid s,a)\), the Markov property, the reward hypothesis, returns (episodic and discounted), policies, the state- and action-value functions, and the Bellman expectation and optimality equations whose solution is the optimal policy. Every later method is an approximate way of solving these equations. Maps to lectures CS3–CS5.

From bandits to MDPs

Bandits taught us to estimate the value of each action in a single situation. MDPs add the missing ingredient of the full problem: actions influence not just immediate rewards but also subsequent situations, or states, and through those, future rewards. So MDPs involve delayed reward and the need to trade off immediate and delayed reward — and the need to estimate the value \(q_*(s,a)\) of each action in each state, or the value \(v_*(s)\) of each state given optimal action selection. These state-dependent quantities are essential to assigning credit correctly for long-term consequences.

The agent–environment interface

MDPs are a straightforward framing of the problem of learning from interaction to achieve a goal. The learner and decision-maker is the agent; the thing it interacts with, comprising everything outside the agent, is the environment. These interact continually: the agent selects actions and the environment responds to those actions and presents new situations to the agent. The environment also gives rise to rewards, special numerical values that the agent seeks to maximize over time through its choice of actions.

Concretely, the agent and environment interact at each of a sequence of discrete time steps \(t=0,1,2,3,\dots\). At each step \(t\) the agent receives some representation of the environment's state \(S_t\in\mathcal{S}\), and on that basis selects an action \(A_t\in\mathcal{A}(s)\). One step later, in part as a consequence, the agent receives a numerical reward \(R_{t+1}\in\mathcal{R}\subset\mathbb{R}\) and finds itself in a new state \(S_{t+1}\). The MDP and agent together give rise to a trajectory: \(S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \dots\)

The dynamics function

In a finite MDP, the sets of states, actions, and rewards (\(\mathcal{S},\mathcal{A},\mathcal{R}\)) all have a finite number of elements. The random variables \(R_t\) and \(S_t\) have well-defined discrete probability distributions dependent only on the preceding state and action. The complete dynamics of the MDP are captured by a single four-argument function \(p\):

This is an ordinary deterministic function of four arguments; it specifies a probability distribution for each choice of \(s\) and \(a\), so \(\sum_{s'}\sum_{r} p(s',r\mid s,a)=1\) for all \(s,a\). The function \(p\) is the model dynamics and it characterizes the environment completely.

Quantities derived from the dynamics

From \(p\) you can compute anything else you need about the environment:

the state-transition probabilities; the expected reward for a state–action pair,

and the expected reward for a state–action–next-state triple,

The Markov property

In an MDP, the probabilities given by \(p\) completely characterize the environment's dynamics. That is, the probability of each possible value for \(S_t\) and \(R_t\) depends only on the immediately preceding state and action \(S_{t-1}, A_{t-1}\), and, given them, not at all on earlier states and actions. This is the Markov property. It is best viewed as a restriction not on the decision process but on the state: the state must include information about all aspects of the past agent–environment interaction that make a difference for the future. If it does, the state is said to have the Markov property. The whole theory of MDPs rests on this assumption.

The agent–environment boundary

The boundary between agent and environment is typically drawn closer to the agent than one might first suppose. Motors, sensors, and even the body are usually considered parts of the environment, not the agent. The general rule: anything that cannot be changed arbitrarily by the agent is considered to be outside of it and thus part of its environment. The boundary represents the limit of the agent's absolute control, not of its knowledge — the agent may know a great deal about how its environment works yet still face a difficult task. The boundary can be located at different places for different purposes.

The framework is abstract and flexible

The MDP framework is a considerable abstraction of the problem of goal-directed learning from interaction. It proposes that whatever the details of the sensory, memory, and control apparatus, and whatever the objective, any problem of learning goal-directed behaviour can be reduced to three signals passing back and forth between an agent and its environment: one signal to represent the choices made by the agent (the actions), one signal to represent the basis on which the choices are made (the states), and one signal to define the agent's goal (the rewards). Time steps need not refer to fixed intervals of real time; actions can be low-level (voltages to motors) or high-level (whether or not to have lunch); states can be low-level sensations or high-level abstract symbolic descriptions. The same framework describes Atari from raw pixels (state = pixels, action = controls, reward = change in score), traffic-signal control, and the recycling robot below.

Worked example — the recycling robot

A mobile robot collects empty soda cans, running on a rechargeable battery. Its high-level decision about how to search is made by an RL agent based on the battery's charge level. Assume only two charge levels can be distinguished, so the state set is \(\mathcal{S}=\{\text{high},\text{low}\}\). In high the actions are \(\{\text{search},\text{wait}\}\); in low they are \(\{\text{search},\text{wait},\text{recharge}\}\). Rewards are zero most of the time, becoming positive when the robot secures a can and negative (\(-3\)) if it depletes the battery and must be rescued. Searching earns more on average than waiting (\(r_{\text{search}} > r_{\text{wait}}\)). The full dynamics fit in one table:

\(s\)	\(a\)	\(s'\)	\(p(s'\mid s,a)\)	\(r(s,a,s')\)
high	search	high	\(\alpha\)	\(r_{\text{search}}\)
high	search	low	\(1-\alpha\)	\(r_{\text{search}}\)
low	search	high	\(1-\beta\)	\(-3\)
low	search	low	\(\beta\)	\(r_{\text{search}}\)
high	wait	high	\(1\)	\(r_{\text{wait}}\)
low	wait	low	\(1\)	\(r_{\text{wait}}\)
low	recharge	high	\(1\)	\(0\)

This table is the MDP — states, actions, transition probabilities, and rewards in one place. Notice every row is a value of \(p(s',r\mid s,a)\), and the rows for each \((s,a)\) sum to probability 1. Given this, the rest of the chapter is about computing how good each state and action is.

Goals and the reward hypothesis

The agent's goal is formalized in terms of the reward signal. The reward hypothesis states: all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal (called reward). Using a reward signal to formalize the idea of a goal is one of the most distinctive features of reinforcement learning.

Reward says the "what", never the "how"

It is critical that the rewards we set up truly indicate what we want accomplished — not how we want it achieved. Reward is not the place to impart prior knowledge about how to achieve the goal; that belongs in the initial policy or value function. Two cautionary examples:

• Chess: the agent should be rewarded only for actually winning, not for subgoals like taking the opponent's pieces. If rewarded for taking pieces, it might find a way to take pieces even at the cost of losing the game — falling for the opponent's trap.
• Vacuum cleaner: if rewarded for each unit of dirt collected, it may learn to repeatedly deposit dirt and then suck it up again to rack up reward, never actually cleaning.

Returns and episodes

If the sequence of rewards after step \(t\) is \(R_{t+1}, R_{t+2}, R_{t+3},\dots\), the agent seeks to maximize the expected return \(G_t\), defined as some specific function of the reward sequence. In the simplest case, the return is the sum of the rewards:

where \(T\) is a final time step. This makes sense when there is a natural notion of a final step — when the agent–environment interaction breaks naturally into subsequences, called episodes (plays of a game, trips through a maze). Each episode ends in a special terminal state, followed by a reset to a standard starting state. Tasks with episodes of this kind are called episodic tasks.

Continuing tasks and discounting

In many cases the interaction does not break into episodes but goes on continually without limit — continuing tasks — so \(T=\infty\), and the simple sum of rewards could itself be infinite. The additional concept needed is discounting. The agent tries to maximize the expected discounted return:

where \(\gamma\), with \(0\le\gamma\le1\), is the discount rate. It determines the present value of future rewards: a reward received \(k\) steps in the future is worth only \(\gamma^{k-1}\) times what it would be worth if received immediately. If \(\gamma<1\), the infinite sum has a finite value as long as the reward sequence is bounded. If \(\gamma=0\) the agent is "myopic" — concerned only with maximizing the immediate reward. As \(\gamma\) approaches 1, the return takes future rewards into account more strongly; the agent becomes more farsighted.

The fundamental recursion

Returns at successive time steps are related to each other in a way that is important for the theory and algorithms of RL:

This works for all \(t

Policies and value functions

A policy is a mapping from states to probabilities of selecting each possible action. If the agent is following policy \(\pi\) at time \(t\), then \(\pi(a\mid s)\) is the probability that \(A_t=a\) if \(S_t=s\). RL methods specify how the agent's policy is changed as a result of its experience. The value function of a state \(s\) under a policy \(\pi\), denoted \(v_\pi(s)\), is the expected return when starting in \(s\) and following \(\pi\) thereafter:

Similarly, the value of taking action \(a\) in state \(s\) under \(\pi\), the action-value function, is

These functions can be estimated from experience — for example by averaging the actual returns that followed each state (which is exactly the Monte Carlo method of Chapter 5).

The Bellman expectation equation

The value function satisfies a recursive relationship analogous to the one for returns. For any policy \(\pi\) and any state \(s\), substitute the recursion \(G_t=R_{t+1}+\gamma G_{t+1}\) into the definition of \(v_\pi\) and expand:

This is the Bellman equation for \(v_\pi\). It expresses a relationship between the value of a state and the values of its successor states. Read it as a weighted average: starting from \(s\), the agent could take any action \(a\) (weighted by \(\pi(a\mid s)\)), the environment could respond with any next state/reward pair (weighted by \(p\)), and for each the value is the immediate reward plus the discounted value of the next state. The value function \(v_\pi\) is the unique solution to this equation. It is the basis of a number of ways to compute, approximate, and learn \(v_\pi\).

Optimal policies and optimal value functions

Solving an RL task means finding a policy that achieves a lot of reward over the long run. A policy \(\pi\) is defined to be better than or equal to \(\pi'\) if its expected return is greater than or equal to that of \(\pi'\) for all states. There is always at least one policy that is better than or equal to all others — an optimal policy, denoted \(\pi_*\). All optimal policies share the same optimal state-value function \(v_*\) and the same optimal action-value function \(q_*\):

The Bellman optimality equation

Because \(v_*\) is the value function of a policy, it satisfies the Bellman equation; but because it is the optimal value function, its consistency condition can be written in a special form without reference to any specific policy — the Bellman optimality equation:

The only change from the expectation equation is that the average over the policy's actions is replaced by a maximum — the value of a state under an optimal policy must equal the expected return for the best action from that state. The Bellman optimality equation is actually a system of equations, one per state; for \(n\) states there are \(n\) equations in \(n\) unknowns.

Reading off the optimal policy — and why it's hard

Once you have \(v_*\), determining an optimal policy is easy: for each state, any action that achieves the maximum in the Bellman optimality equation is an optimal action. So any policy that is greedy with respect to \(v_*\) is an optimal policy. With \(q_*\) it is even easier — no one-step lookahead is needed: \(\pi_*(s)=\arg\max_a q_*(s,a)\). The beauty of \(v_*\) is that a greedy policy that is short-sighted with respect to \(v_*\) is in fact optimal in the long term, because \(v_*\) already accounts for the reward consequences of all future behaviour.

Lecture map & recap

Idea	Slide / next use
Agent–environment interface, dynamics \(p\), Markov	CS3–CS4
Recycling robot, reward hypothesis	CS4
Returns, discounting, episodic vs continuing	CS4–CS5
Policy, \(v_\pi\), \(q_\pi\), Bellman equations	CS5; solved in Ch 4–5

References & next

• Chapter 4 — Dynamic Programming → · solving a known MDP
• ← Chapter 2 — Multi-armed Bandits
• CS3–CS5 — Slides Explained · the lecture version