Chapter 3: Finite Markov Decision Processes

English MDPs are meant to be a straightforward framing of the problem of learning from interaction to achieve a goal. The learner and decision maker is called the agent. The thing it interacts with, comprising everything outside the agent, is called the environment. These interact continually, the agent selecting actions and the environment responding to these actions and presenting new situations to the agent. The environment also gives rise to rewards, special numerical values that the agent seeks to maximize over time.

English At each of a sequence of discrete time steps t=0,1,2,..., the agent receives a representation of the environment's state S_t∈S, selects an action A_t∈A(s). One step later, it receives a reward R_t+1∈R and finds itself in a new state S_t+1. This gives rise to a trajectory: S₀,A₀,R₁,S₁,A₁,R₂,...

English In a finite MDP, the sets of states, actions, and rewards 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:

English The function p defines the dynamics of the MDP. From p we can derive state-transition probabilities p(s'|s,a) = Σ_r p(s',r|s,a) and expected rewards r(s,a,s') or r(s,a).

English The agent's goal is formalized in terms of a special signal called the reward. The agent's goal is to maximize the total amount of reward it receives — not immediate reward, but cumulative reward in the long run. We can state this as the reward hypothesis:

"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)."

English The return G_t is the function of future rewards that the agent seeks to maximize. For episodic tasks (which naturally break into subsequences called episodes, e.g., games, maze runs):

English For continuing tasks (which go on without limit), we use discounting. The agent chooses actions to maximize the expected discounted return:

English where γ (0≤γ≤1) is the discount rate. If γ=0, the agent is "myopic" — only concerned with immediate rewards. As γ→1, the agent becomes more farsighted. A critical recursive relationship holds: G_t = R_t+1 + γG_t+1

English We unify episodic and continuing tasks by considering episode termination as entering a special absorbing state that transitions only to itself and generates only zero rewards. This way the same return formula works for both cases, and we include the possibility that T=∞ or γ=1 (but not both).

English A policy is a mapping from states to probabilities of selecting each possible action: π(a|s) = Pr{A_t=a | S_t=s}. Reinforcement learning methods specify how the agent's policy is changed as a result of its experience.

English The value function of a state s under policy π, denoted v_π(s), is the expected return when starting in s and following π thereafter:

English The value of taking action a in state s under policy π, denoted q_π(s,a), is the expected return starting from s, taking a, and thereafter following π:

English A fundamental property: value functions satisfy recursive relationships. The Bellman equation for v_π expresses the value of a state in terms of the values of its successor states:

English Solving a RL task means finding a policy that achieves a lot of reward over the long run. A policy π is better than π' if v_π(s) ≥ v_π'(s) for all s. There is always at least one optimal policy π*. All optimal policies share the same optimal state-value function and optimal action-value function:

English The Bellman optimality equation expresses the fact that the value of a state under an optimal policy must equal the expected return for the best action from that state:

English Key insight: Once we have v*, determining an optimal policy is easy — for each state, find the action that achieves the maximum in the Bellman optimality equation (a one-step search). Having q* makes it even easier: simply find any action that maximizes q*(s,a), without needing to know anything about the environment's dynamics.

English Explicitly solving the Bellman optimality equation provides one route to finding an optimal policy, but this solution relies on three assumptions rarely true in practice: (1) we accurately know the environment's dynamics; (2) we have enough computational resources; (3) the Markov property. For example, backgammon has ~10²⁰ states — it would take thousands of years to solve exactly.

English Many different decision-making methods can be viewed as ways of approximately solving the Bellman optimality equation. The online nature of reinforcement learning makes it possible to approximate optimal policies in ways that put more effort into learning for frequently encountered states, at the expense of less effort for infrequently encountered states.

English Reinforcement learning is about learning from interaction how to behave to achieve a goal. Key elements: actions (choices by agent), states (basis for choices), rewards (basis for evaluation). A policy is a stochastic rule for selecting actions. The return is what the agent maximizes. Value functions assign expected returns to states or state-action pairs. Optimal value functions assign the largest achievable expected return. The Bellman optimality equations are consistency conditions that optimal value functions must satisfy.

English In complete knowledge problems, the agent has a complete model of the environment's dynamics. In incomplete knowledge problems, no such complete model is available. Even with a complete model, the agent typically cannot perform enough computation per time step to fully use it. A well-defined notion of optimality organizes our approach but is an ideal that agents can only approximate.