Reinforcement Learning
Bellman Equations
Value functions are useful because a long-term prediction can be decomposed recursively. The value of being somewhere is determined by what happens immediately and the value of where we end up afterward:
\[ V^\pi(s) = \mathbb E_{a\sim\pi,\;s'\sim P} \left[ r(s,a,s')+\gamma V^\pi(s') \right]. \]This is the Bellman equation. Rather than separately reasoning about every possible complete future trajectory, it relates the value of the present state to the value of possible next states.
For an optimal agent, the corresponding relationship is
\[ V^*(s) = \max_a \mathbb E_{s'\sim P} \left[ r(s,a,s')+\gamma V^*(s') \right]. \]The \(\max\) appears because an optimal agent chooses whichever available action produces the greatest expected future return.
What Can Be Learned?
An RL algorithm must somehow discover behaviour that produces high expected return, but there are several different objects it might learn.
A policy optimization method directly adjusts the parameters of the policy
\[ \pi_\theta(a\mid s) \]so that actions producing higher return become more likely. Policy-gradient methods are examples of this approach. Alternatively, the agent can learn a value function such as
\[ Q(s,a) \]and derive its behaviour from it by choosing actions with high estimated value. These are Q-learning methods.
Many algorithms combine both ideas. An actor--critic method learns a policy, the actor, alongside a value function, the critic, which provides information useful for improving that policy.
Models of the Environment
A separate distinction concerns whether the agent learns or uses a model of how the environment works. A model predicts what will happen after an action, for example
\[ P(s_{t+1}\mid s_t,a_t) \]and possibly the resulting reward.
In model-based RL, the agent has or learns such a model and can use it to plan by considering possible future consequences before acting:
\[ \text{possible action} \rightarrow \text{predicted future} \rightarrow \text{evaluate} \rightarrow \text{choose}. \]In model-free RL, the agent instead learns a policy or value function without explicitly learning a model that it uses for planning.
A learned model can make experience more useful because the agent can reason about possible futures without physically experiencing every one of them. However, errors in the model can also produce poor plans, and learning an accurate model may itself be difficult.
On-Policy and Off-Policy Learning
RL algorithms also differ in which experience they can learn from. An on-policy method learns primarily from trajectories generated by the policy currently being optimized. If the policy changes substantially, older experience may no longer provide the right distribution of examples.
An off-policy method can learn about one policy using experience generated by another policy. This makes it possible to reuse older experience or learn from data produced by other behaviours.
There is therefore a recurring tradeoff between sample efficiency, how much learning we obtain from each interaction with the environment, and other desirable properties such as simplicity and stability.
Markov Decision Processes
The objects discussed above can be collected into a formal description of the decision problem. Accordingly, a Markov Decision Process (MDP) contains a state space \(S\), action space \(A\), transition model \(P\), reward function \(R\), and initial-state distribution \(\rho_0\):
\[ \langle S,A,P,R,\rho_0\rangle. \]The important assumption is not the notation itself but the Markov property: once the current state \(s_t\) is known, the earlier history contains no additional information needed to predict the next state,
\[ P(s_{t+1}\mid s_0,a_0,\ldots,s_t,a_t) = P(s_{t+1}\mid s_t,a_t). \]The state must therefore contain everything from the past that remains relevant for predicting what happens next. This explains why defining the state of a problem is substantive rather than choosing notation. If information from the past still matters after \(s_t\) is specified, then what we called the "state" was not actually a complete Markov state.
For a concrete sequential problem, the modeling task therefore is to ask: what is actually true at time \(t\); what can the agent observe; what can it do; how does its action change the world; and what outcomes are rewarded? The objects
\[ s_t,\qquad o_t,\qquad a_t,\qquad P,\qquad R,\qquad \pi \]arise as answers to these questions rather than as pieces of notation to impose on the problem.