Week 1: Reinforcement Learning Problem Formulation

Reinforcement learning studies sequential decision making under uncertainty. Unlike supervised learning, where data is static, an RLReinforcement Learning agent's actions actively influence future states and rewards, creating a closed feedback loop.

Purpose of this lecture#

The core question in reinforcement learning is how to express goal-directed behavior with a single mathematical objective.

Reinforcement learning formalizes this by maximizing expected cumulative reward. Translating this objective into practical algorithms introduces three core problems:

1. Reward specification. Specifying reward functions precisely is difficult. A misspecified reward leads an agent to optimize the literal reward signal while violating the intended goal.

2. Uncertainty over time. Environments are stochastic and often partially observable. The agent must evaluate actions whose delayed consequences unfold over time.

3. Computational tractability. Maximizing an infinite sum of future rewards directly is intractable. Computing solutions requires recursive structure.

This lecture addresses these problems with the MDPMarkov Decision Process formalism, value functions, and the Bellman equations. These concepts provide the mathematical encoding of sequential decision making. Later algorithms, including tabular methods, deep RLReinforcement Learning, RLHFReinforcement Learning from Human Feedback, and GRPOGroup Relative Policy Optimisation, build directly on this theory.

This lecture derives the Bellman equations from first principles, examines where the Markov assumption fails in practice, and presents the engineering techniques used to address partial observability.

Sequential decision making#

In reinforcement learning, an agent interacts with an environment over discrete time steps. This interaction forms a closed feedback loop:

• At time step $t$, the agent observes a state $s_t$
• It selects an action $a_t$
• The environment transitions to a new state $s_{t+1}$
• The agent receives a scalar reward $r_{t+1}$

The agent's objective is not to maximize immediate reward, but to act so as to maximize cumulative reward over time.

This temporal coupling distinguishes reinforcement learning from:

• Supervised learning, where data is fixed and independent of the learner's actions
• Standard optimization, where decisions are made once rather than sequentially

The notation $r_{t+1}$ for the reward received after taking action $a_t$ follows the Sutton and Barto convention: reward is indexed by the time step at which the agent receives it, rather than when the action occurred. This notation is standard across RL literature.

Formalizing "maximize cumulative reward over time" requires two components: an environment model (an MDPMarkov Decision Process) and an accumulation criterion (the return). We begin with the reward hypothesis, which formalizes the scalar objective.

The reward hypothesis#

A foundational premise in reinforcement learning is the Reward Hypothesis:

“

All goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal (reward).

This hypothesis asserts that complex behaviors, such as playing games or robotic locomotion, can be framed as maximizing expected cumulative reward. It is a working hypothesis rather than a mathematical theorem, and much of modern reinforcement learning explores its practical limits.

A concrete starting point#

Before examining where the hypothesis succeeds and fails, consider the simplest case where it clearly works.

Gridworld navigation. An agent moves through a $4 \times 4$ grid to reach a goal cell in the lower-right corner. The reward function assigns $+1$ upon reaching the goal and $0$ at every other step. This is unambiguous and easy to specify. An agent maximizing expected cumulative reward will learn to navigate efficiently to the goal. The reward hypothesis applies cleanly.

Atari Pong. Reward is $+1$ when the agent scores a point and $-1$ when the opponent scores. This objective is also unambiguous. Mnih et al. (2013) demonstrated that DQNDeep Q-Network learned competitive policies directly from pixel inputs and score deltas, providing early empirical support for the hypothesis.

These cases share a key property: the reward function captures the intended goal. The difficulty arises when the written reward diverges from the desired behavior.

Why reward design matters#

The hypothesis does not prescribe how to design reward functions. Reward specification remains a central challenge in RLReinforcement Learning. The same principles apply directly to RLHFReinforcement Learning from Human Feedback, preference optimization (GRPOGroup Relative Policy Optimisation, DPODirect Preference Optimization, PPOProximal Policy Optimisation), and autonomous agents. Three common failure modes arise:

• Sparse rewards: signal arrives only at task completion, making learning slow
• Dense rewards: accelerate learning but risk reward hacking
• Reward misspecification: the gap between the written reward and the actual goal

The tension between what is easy to specify and what is safe to optimize is a recurring theme across RL.

With the reward hypothesis establishing the scalar objective, we next formalize the environment: the mathematical framework defining how actions yield transitions and rewards.

Markov decision processes (MDPs)#

The canonical mathematical model for reinforcement learning is the Markov Decision Process (MDPMarkov Decision Process).

An MDPMarkov Decision Process is defined by the tuple:

where:

• $\mathcal{S}$ is the state space,
• $\mathcal{A}$ is the action space,
• $P(s' \mid s, a)$ is the transition probability kernel,
• $R(s, a)$ is the expected reward function,
• $\gamma \in [0,1)$ is the discount factor.

The Markov property#

The defining assumption of an MDPMarkov Decision Process is the Markov property:

The future is conditionally independent of the past given the current state and action. The current state $s_t$ contains all information relevant to predicting what happens next.

Markovianity is engineered, not given#

In practice, raw sensor observations are rarely Markovian. This distinction is fundamental to reinforcement learning system design.

Consider a robot arm that measures joint angles but not joint velocities. The subsequent state depends directly on momentum, which is absent from position measurements alone. Two robots with identical joint angles but different velocities transition to different subsequent states, making the transition dynamics non-Markovian in the observed state. Similarly, a language model observing only the latest token cannot distinguish between different meanings of polysemous words. In both cases, the current observation fails to capture the true underlying state.

Systems where the agent receives observations $o_t$ generated by an underlying hidden state $x_t$ are modeled as Partially Observable Markov Decision Processes (POMDPs):

POMDPs represent the general case; MDPs represent the special case where $o_t = x_t$. Most physical systems and real-world problems are POMDPs.

Three standard engineering techniques address partial observability:

• State augmentation: incorporate physical derivatives, such as velocities or acceleration signals, directly into the state vector.
• Observation stacking: concatenate a temporal window of recent observations, as in Atari frame stacking.
• Recurrent representations: maintain a recurrent state vector via an LSTM or transformer architecture to track belief states over time.

Language models as MDPs#

To ground this abstraction, consider RLReinforcement Learning applied to large language models, as in RLHFReinforcement Learning from Human Feedback:

Under this formulation, text generation is a sequential decision process, and preference alignment algorithms operate as reinforcement learning methods in this MDP. Because the state includes the prompt and all generated tokens within the context window, the MDP formulation satisfies the Markov property for the sequence.

With the environment formalized as an MDPMarkov Decision Process, the agent's behavior must be specified. A policy defines how the agent maps states to actions, and its properties determine whether the agent can learn effectively.

Policies#

A policy specifies the agent's behavior as a mapping from states to actions:

Policies may be:

• Deterministic: $\pi(s) = a$, selecting a single action per state. Common in deployment and in control-theoretic settings.
• Stochastic: sampling actions from a probability distribution. Essential for exploration during training, and fundamental to policy gradient methods.

In LLMs, the policy is the language model itself: a stochastic policy over the vocabulary at each token position, with temperature controlling the degree of stochasticity.

Given a policy, we evaluate its quality across trajectories using the return.

Returns and discounting#

The agent's objective is formalized via the return, the discounted cumulative reward from time step $t$ onward:

This formulation reflects three distinct mathematical interpretations.

Three interpretations of the discount factor $\gamma$#

1. Convergence guarantee. For continuing tasks, the infinite sum $\sum_{k=0}^\infty r_{t+k+1}$ diverges if rewards are bounded away from zero. When $\gamma < 1$, the return is bounded by $G_t \leq R_{\max} / (1 - \gamma)$. This condition is a mathematical requirement for infinite horizons.

2. Time preference. The discount factor $\gamma$ balances immediate rewards against delayed rewards. As $\gamma \to 1$, future rewards receive comparable weight to immediate ones. As $\gamma \to 0$, the agent prioritizes immediate reward. The effective planning horizon is approximately $1/(1-\gamma)$ steps because $\sum_{k=0}^\infty \gamma^k = 1/(1-\gamma)$.

3. Survival probability. The factor $\gamma$ can represent the probability that an interaction continues at each step. With termination probability $1 - \gamma$, the expected horizon matches geometric discounting. This perspective unifies episodic and continuing formulations under a single framework.

A warning on $\gamma$ and policy gradient bias#

In policy gradient methods, using $\gamma < 1$ introduces an objective discrepancy. The discounted policy gradient does not match the gradient of the undiscounted return. This discrepancy matters in continuing tasks where the ultimate objective is undiscounted cumulative reward. We return to this derivation in later lectures.

Episodic vs continuing tasks#

• Episodic tasks terminate at a terminal state (games, robotic manipulation episodes, single LLMLarge Language Model responses). The return is a finite sum.
• Continuing tasks run indefinitely (control systems, long-running agents). The return requires discounting for finiteness.

For episodic tasks, terminal states are often treated as absorbing states with zero reward and self-loops: once reached, the agent stays there and receives zero reward forever. This unifies the episodic and continuing formalisms and is the standard implementation in most RLReinforcement Learning libraries.

The return $G_t$ is a random variable that depends on transition dynamics, policy stochasticity, and trajectory length. We evaluate policies by computing the expected return, which defines the value function.

Value functions#

Value functions quantify expected return from states and actions under policy $\pi$. They are not directly observable; algorithms estimate them from experience or derive them from an environment model.

State-value function#

This is the expected cumulative discounted reward, starting from state $s$ and following policy $\pi$ thereafter.

Action-value function (Q-function)#

This conditions on both state and action: the expected return from taking action $a$ in state $s$, then following $\pi$.

The relationship between them:

Value functions turn sequential decision problems into expected return estimation. The optimal value functions $V^*$ and $Q^*$ determine optimal policies directly: $\pi^*(s) = \arg\max_a Q^*(s,a)$.

Because infinite horizon returns cannot be evaluated by exhaustive summation, reinforcement learning relies on recursive representations. The Bellman equations express the value of each state in terms of expected successor state values.

Bellman equations#

The Bellman equations express value functions recursively, relating the value of the current state to the values of successor states. They define the computational foundation of reinforcement learning.

Bellman expectation equation#

This formulation constitutes a system of $|\mathcal{S}|$ linear equations in $V^\pi$. Given policy $\pi$, transition model $P$, and reward function $R$, solving for $V^\pi$ requires solving a linear algebra problem. This process is called policy evaluation.

Bellman optimality equation#

This formulation is a nonlinear fixed-point equation in $V^*$. Because the $\max$ operator is nonlinear, $V^*$ cannot be solved by matrix inversion. It possesses a unique solution that iterative methods reach geometrically.

The contraction mapping property#

Define the Bellman optimality operator $\mathcal{T}$:

$\mathcal{T}$ is a $\gamma$-contraction in the $\ell_\infty$ norm:

By the Banach fixed-point theorem, repeated application of $\mathcal{T}$ converges geometrically to the unique fixed point $V^*$ at rate $\gamma$ per iteration. This process constitutes value iteration. The contraction property explains why $\gamma < 1$ is an algorithmic necessity: setting $\gamma = 1$ removes the contraction guarantee.

Connection to the LQR Riccati equation#

This subsection provides optional background connecting dynamic programming to classical control. Readers familiar with robotics control will recognize the Bellman optimality equation in the following continuous-state form.

Consider linear dynamics $s_{t+1} = As_t + Ba_t$ with quadratic cost, known as the Linear Quadratic Regulator (LQR). Let $A$ represent the state-transition matrix, $B$ the input matrix, $Q_c$ the state-cost matrix, and $R_c$ the action-cost matrix. We use subscript $c$ to distinguish cost matrices from reward functions. The discrete-time Algebraic Riccati Equation (DARE) is:

This equation is the Bellman optimality equation specialized to linear quadratic systems, where matrix $P$ parameterizes the quadratic value function. LQR solves optimal control in closed form under these linear-quadratic assumptions.

Worked example: Bellman backup on a two-state MDP#

Setup. Consider the following MDPMarkov Decision Process:

• States: $\mathcal{S} = \{s_1,\, s_2\}$
• Actions: $\mathcal{A} = \{\text{stay},\, \text{switch}\}$
• Transitions: deterministic. Action stay keeps the agent in the current state, and action switch moves the agent to the other state.
• Rewards: $R(s_1, \cdot) = 1$, $R(s_2, \cdot) = 0$ (reward depends only on the state).
• Discount: $\gamma = 0.9$.

Policy $\pi_1$ (always stay). The Bellman expectation equations are:

Solving the linear system:

Interpretation. Starting in $s_1$, the agent collects $+1$ at every step. The geometric series $\sum_{k=0}^\infty 0.9^k = \frac{1}{1-0.9} = 10$ confirms the analytical result. Starting in $s_2$, the agent receives zero reward indefinitely.

Policy $\pi_2$ (always switch). The agent alternates between $s_1$ and $s_2$, receiving rewards $1, 0, 1, 0, \ldots$. The Bellman equations couple both states:

Substituting the second equation into the first yields $V^{\pi_2}(s_1) = 1 + 0.81\, V^{\pi_2}(s_1)$, which gives $V^{\pi_2}(s_1) = \frac{1}{0.19} \approx 5.26$.

Conclusion. Policy $\pi_1$ strictly dominates policy $\pi_2$ because $V^{\pi_1}(s_1) = 10 > 5.26 = V^{\pi_2}(s_1)$. The optimal policy stays in $s_1$ to maximize cumulative return, matching the choice selected by the Bellman optimality operator.

Browser lab: iterative policy evaluation#

Implement the policy evaluation above using the iterative (not direct) method, and verify convergence to the analytical solution.

import numpy as np

# MDP definition
gamma = 0.9

# States: 0 = s1, 1 = s2. Actions: 0 = stay, 1 = switch.
# P[s, a, s'] = P(s' | s, a)
P = np.array([
    [[1.0, 0.0], [0.0, 1.0]],   # from s1: stay->s1, switch->s2
    [[0.0, 1.0], [1.0, 0.0]],   # from s2: stay->s2, switch->s1
])
R = np.array([1.0, 0.0])        # R(s1) = 1, R(s2) = 0

# Policy pi1: always stay (action 0 in both states)
pi = np.array([0, 0])

# Iterative policy evaluation
# Initial guess of zeros. The contraction property guarantees convergence
# regardless of the starting estimate.
V = np.zeros(2)
for i in range(1000):
    # Bellman expectation backup: R(s) + γ Σ_{s'} P(s'|s,π(s)) V(s')
    # np.dot computes the expected future value over successor states.
    V_new = np.array([
        R[s] + gamma * np.dot(P[s, pi[s]], V)
        for s in range(2)
    ])
    # Convergence check using the infinity norm (max absolute difference).
    # A small value means we've reached the fixed point of the Bellman operator.
    if np.max(np.abs(V_new - V)) < 1e-8:
        print(f"Converged after {i+1} iterations")
        break
    # Synchronous (Jacobi-style) update: all states updated using the old V.
    V = V_new

print(f"V(s1) = {V[0]:.4f}")   # Expected: 10.0
print(f"V(s2) = {V[1]:.4f}")   # Expected: 0.0
# Always-stay: V(s1) = 1/(1-γ) = 10 under perpetual reward 1.
print("Notice: under π=always stay, s2 is never left and has R=0 → V(s2)=0.")

Try it: Change to pi = np.array([1, 1]) (always switch) and re-run. The value converges to $V(s_1) \approx 5.26$. Policy evaluation computes values for a fixed policy; subsequent weeks explore policy optimization.

Taxonomy of reinforcement learning problems#

Classifying reinforcement learning problems guides algorithm selection and clarifies necessary assumptions.

Bandits vs full MDPs#

• Multi-armed bandits: no state transitions occur; actions yield immediate rewards. The agent balances exploration of uncertain actions against exploitation of high-value actions.
• Full MDPs: actions influence subsequent states and long-term returns. Local bandit reasoning applies within each state, but value functions account for delayed transitions.

Bandits appear throughout reinforcement learning applications, including recommendation systems, online experimentation, and pairwise preference models in RLHFReinforcement Learning from Human Feedback.

Online vs offline reinforcement learning#

• Online RL: the agent collects experience while learning. Transitions originate from current or recent policies. Common algorithms, such as Q-learning, PPOProximal Policy Optimisation, and SACSoft Actor-Critic, operate online.
• Offline RL: the agent learns from a fixed dataset collected by a behavior policy, without active environment interaction. This paradigm is essential in domains such as robotics and healthcare where exploratory actions carry high cost or risk.

The primary technical challenge in offline reinforcement learning is distributional shift. The learned policy can select state-action pairs rare or missing in the dataset. Without environment interaction, erroneous value estimates remain uncorrected, yielding inflated Q-values. Supervised learning avoids this issue because classifiers do not generate sequential trajectories in low-density data regions.

Model-free vs model-based RL#

• Model-free RL: learns value functions or policies directly from experience without constructing an explicit transition model $P$.
• Model-based RL: constructs or queries an explicit transition model to plan actions, improving sample efficiency at the risk of model bias.

These paradigms form a continuum. Dyna algorithms combine environment transitions with rollouts simulated from a learned model. Dreamer and MuZero plan inside learned latent-state representations rather than physical observation spaces.

Relationship to supervised learning and control theory#

Supervised learning#

Supervised learning optimizes a fixed loss on static datasets where outputs do not alter subsequent data. Reinforcement learning violates this assumption. The policy selects actions that determine subsequent states and collected transitions, forming a non-stationary feedback loop that requires managing exploration.

Control theory#

Classical control theory addresses sequential decision making under distinct assumptions:

• Known dynamics: classical control assumes analytical access to transition dynamics $P$, whereas reinforcement learning generally estimates them from data or operates model-free.
• Stability guarantees: control theory emphasizes Lyapunov stability and robustness criteria that general reinforcement learning rarely guarantees.
• Function approximation: classical control focuses on low-dimensional analytical representations, whereas reinforcement learning scales to high-dimensional state spaces using neural network approximations.

These formulations intersect directly. Linear Quadratic Regulation (LQR) solves optimal control in closed form for linear dynamics and quadratic costs. Reinforcement learning generalizes this formulation to unknown dynamics and non-linear function approximators.

Connections to modern methods#

The MDP formalism provides the mathematical foundation for modern reinforcement learning architectures. The following examples illustrate how the formal components map to current methods.

DreamerV3: Bellman backups in latent space#

DreamerV3 (Hafner et al., 2023) learns visual control tasks across domains, including robotics and video games, directly from pixel observations. Its architecture instantiates the MDP tuple:

Once the world model is trained, the agent applies Bellman updates to imagined trajectories without querying the environment. Value iteration operates directly in latent space.

TD-MPC: value-weighted planning#

TD-MPC (Hansen et al., 2022) combines model predictive control with value learning:

• A learned latent world model provides short-horizon rollouts for local transition dynamics $P$.
• A learned action-value function $Q^*(s, a)$, updated via Bellman optimality backups, estimates long-term returns beyond the rollout window.
• Trajectory optimization evaluates action sequences by combining simulated short-term rewards with terminal Q-value estimates.

The Bellman Q-function summarizes delayed returns, allowing the planner to truncate rollouts while retaining long-horizon evaluation.

Common pitfalls in RL problem formulation#

Recognizing common formulation errors prevents systematic failures in implementation:

1. Non-Markovian state representation. Using raw observations without establishing state sufficiency causes value estimates to oscillate. Verify whether identical observations from different histories transition to different outcomes. Restore Markovianity using state augmentation or observation stacking.

2. Reward hacking. Optimizing a proxy reward that diverges from true intent produces unintended behaviors that maximize numerical reward. Before training, evaluate potential degenerate policies. For instance, rewarding joint velocities alone causes a walking robot to fall forward.

3. Setting $\gamma = 1$ in continuing tasks. Infinite-horizon sums diverge and Bellman operators lose their contraction property, producing numerical overflow. Set $\gamma < 1$, or formulate the task as episodic with absorbing terminal states.

4. Confusing episodic and continuing formulations. Fixed-duration manipulation tasks are episodic, whereas continuous process control is continuing. Select the formulation based on whether natural terminal states exist. Continuing formulations require discounting to preserve finite returns.

5. Ignoring distributional shift in offline RL. Training on static datasets without penalizing out-of-distribution actions causes overoptimistic value estimates. Unlike supervised learning, bootstrapped value estimation compounds extrapolation errors on unsupported state-action pairs.

Key takeaways#

The concepts introduced here form the foundation for every algorithm in the course. The reward hypothesis formalizes goal-directed behavior as scalar reward maximization. Markov decision processes formalize the sequential interaction between agent and environment. Policies specify actions across states, and value functions evaluate expected long-term return.

The Bellman equations express value functions recursively, yielding a linear system for policy evaluation and a nonlinear fixed-point equation for optimality. The contraction mapping property ensures that iterative dynamic programming converges to the unique optimal value function. The discount factor bounds returns in infinite-horizon tasks and defines the effective planning horizon. Finally, the connection to the Riccati equation demonstrates that reinforcement learning extends classical optimal control to systems with unknown dynamics.

Conceptual questions#

1. A robot observes only joint positions, not velocities. Explain why this observation model violates the Markov property. Propose two state engineering strategies to restore approximate Markovianity, and specify what each strategy assumes about the system.

2. Suppose you run value iteration with $\gamma = 1.0$ on a continuing task with bounded positive rewards. Explain why returns diverge, and describe why the Bellman optimality operator loses its contraction property. What minimal modification restores convergence?

3. A language model trained with RLHFReinforcement Learning from Human Feedback achieves high preference scores but generates persuasive yet factually incorrect responses. Analyze this outcome using the reward hypothesis and reward misspecification. How should the training objective be adjusted to mitigate this behavior?

4. Compare the Bellman expectation equation for policy evaluation with the linear system $Ax = b$. Identify $A$, $x$, and $b$, and prove that $A$ is invertible for any $\gamma < 1$.

5. An offline reinforcement learning policy is trained on robot manipulation demonstrations. The policy succeeds on configurations close to the training demonstrations but fails on novel configurations. Contrast this failure mode with compounding imitation error in behavioral cloning.

Knowledge Check#

Check the MDP building blocks from this week.

Looking ahead#

The next lecture examines multi-armed bandits, the simplest non-trivial reinforcement learning problem. Bandits isolate the trade-off between exploration and exploitation without state transitions. Regret analysis and bandit algorithms provide tools that generalize to full MDPs and to preference feedback mechanisms in later lectures.

Further reading#

• Bellman, R. (1957). Dynamic Programming. Princeton University Press. Foundational text introducing the Bellman equation and the principle of optimality.
• Sutton & Barto (2018). Reinforcement Learning: An Introduction (2nd ed.), Chapter 3: Finite Markov Decision Processes. Standard textbook reference.
• Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley. Comprehensive mathematical treatment of dynamic programming convergence and contraction proofs.
• Silver, D. (2015). UCL Course on RL, Lecture 2: Markov Decision Processes. Lecture slides and video covering tabular MDP examples.
• Bertsekas, D. P. (2019). Reinforcement Learning and Optimal Control. Athena Scientific. Bridges classical optimal control and modern reinforcement learning.