Reinforcement Learning: Policy, Value, and the Credit Assignment Problem

RL is the framework where an agent learns by interacting with an environment — no labels, just rewards. The central difficulty is credit assignment: which of the 200 actions in a chess game caused the win? Policy gradient methods and Q-learning solve this differently. Deep Q-Networks applied it to Atari. RLHF applied it to language models. This is the core loop.

Supervised learning requires labelled data. You have inputs and correct outputs; the loss function tells the model how wrong it was. Reinforcement learning replaces labels with rewards: the agent takes actions, the environment returns a reward signal, and the agent learns to act so as to maximise cumulative reward. No one tells the agent which action was correct — it must discover this through interaction.

The RL setup

At each timestep, the agent observes a state s, selects an action a, receives a reward r, and transitions to a new state s'. The environment determines the transition dynamics and reward function. The agent's goal: maximise the expected sum of discounted rewards: E[Σ γ^t * r_t], where γ < 1 is the discount factor, down-weighting future rewards (a reward now is worth more than the same reward later, and uncertainty grows with time).

The credit assignment problem

If a chess game lasts 200 moves and the agent wins, which of the 200 actions were good? The reward (win/lose) arrives at the end; most of the game received reward = 0. Assigning credit to the actions that caused the win — and blame to the ones that caused mistakes — is the central challenge of RL. All RL algorithms are, in some sense, solutions to this problem.

Value functions: predicting future reward

The value function V(s) is the expected cumulative discounted reward starting from state s and following policy π. V(s) = E_π[Σ γ^t * r_t | s_0 = s]. If V(s) is known, credit assignment becomes tractable: an action was good if the state it led to has higher value than expected. The Bellman equation decomposes the value recursively: V(s) = E[r + γ * V(s')]. This recursive structure is the key to learning value functions without waiting for the episode to end.

The Q-function (action-value function) extends this to state-action pairs: Q(s, a) = E[r + γ * max_a' Q(s', a')]. Q(s,a) gives the expected return from taking action a in state s, then acting optimally. The optimal policy is greedy with respect to Q: always take the action with the highest Q value.

Q-learning: learning value functions directly

Q-learning (Watkins, 1989) learns Q(s,a) by iterating the Bellman equation: Q(s,a) ← Q(s,a) + α * (r + γ * max_a' Q(s',a') - Q(s,a)). The term in parentheses is the TD (temporal difference) error — how much the current Q estimate is wrong. This update is applied after every step, propagating reward signals backward through the Q estimates over many episodes.

Deep Q-Networks (DQN, Mnih et al., 2015) replaced the tabular Q function with a neural network — the same network takes the state as input and outputs Q values for all actions. Two crucial stabilisation tricks: experience replay (store transitions (s,a,r,s') in a buffer, sample random mini-batches for training — breaks correlation between consecutive updates) and target network (use a slower-updating copy of the network to compute the TD targets — prevents the chasing-a-moving-target instability). DQN achieved human-level performance on 49 Atari games from raw pixels.

Policy gradient methods: directly optimising the policy

Instead of learning a value function and deriving a policy, policy gradient methods directly parameterise the policy π_θ(a|s) and optimise expected reward. The REINFORCE algorithm: collect a full episode, compute the return G_t = Σ γ^k * r_{t+k} for each step, update: θ ← θ + α * G_t * ∇_θ log π_θ(a_t|s_t). This is the policy gradient theorem — the gradient of expected reward is the expected product of the policy gradient and the return.

The problem: high variance. G_t is a noisy estimate because it depends on the full episode's randomness. Actor-critic methods reduce variance by replacing G_t with the advantage A(s,a) = Q(s,a) - V(s) — how much better is this action than average? The critic (a value function estimator) provides this baseline.

PPO: the practical standard

Proximal Policy Optimisation (Schulman et al., 2017) is the workhorse algorithm for modern RL. It clips the policy update to prevent the new policy from deviating too far from the old one: L = E[min(ratio * A, clip(ratio, 1-ε, 1+ε) * A)]. This clipping provides stability without the complexity of trust region methods. PPO is the algorithm behind most DeepMind and OpenAI game-playing agents.

RLHF: applying RL to language models

Reinforcement Learning from Human Feedback (RLHF) is the training method behind InstructGPT, Claude, and GPT-4. A language model generates responses; human raters rank them; a reward model is trained on these rankings; PPO fine-tunes the language model to maximise the reward model's score, with a KL penalty against the original model to prevent reward hacking. The KL term is exactly the credit assignment constraint: the language model should improve while not drifting too far from learned language structure.

Try on Colab: implement a DQN on OpenAI Gym's CartPole-v1 from scratch — a neural network Q function, experience replay buffer, ε-greedy exploration, and target network. CartPole is solvable in under 1000 episodes. Then remove experience replay and observe training instability. Remove the target network and observe divergence. Each ablation reveals why these tricks were necessary.