Reinforcement Learning

An MDP is the mathematical framework for RL. It consists of: S (states), A (actions), P(s'|s,a) (transition probabilities), R(s,a) (reward function), and γ (discount factor). The Markov property means the next state depends only on the current state and action, not history. An agent interacts with the MDP by choosing actions to maximize cumulative discounted reward: G_t = Σ γ^k r_{t+k}. Almost all RL problems are modeled as MDPs.

A policy π(a|s) is the agent's decision rule — it maps states to action probabilities. A value function V^π(s) measures how good a state is under policy π: the expected cumulative discounted reward from state s. The action-value function Q^π(s,a) extends this to state-action pairs. The goal of RL is to find the optimal policy π* that maximizes V(s) for all states. Value functions help evaluate and improve policies without exhaustive search.

The Bellman equation expresses the recursive relationship between a state's value and its successors: V(s) = max_a Σ P(s'|s,a)[R(s,a) + γ V(s')]. It says the value of a state equals the immediate reward plus the discounted value of the best next state. This decomposition is the foundation of dynamic programming in RL. The Bellman optimality equations define the unique optimal value functions V* and Q* that correspond to the optimal policy.

ε-greedy balances exploration and exploitation: with probability ε the agent picks a random action (explore), and with probability 1−ε it picks the action with the highest estimated Q-value (exploit). Early in training ε is large (e.g., 1.0) to encourage exploration; it decays over time (e.g., to 0.01) as the agent learns. This simple strategy prevents the agent from getting stuck in suboptimal policies while still leveraging learned knowledge.

import random
def epsilon_greedy(Q, state, epsilon):
    if random.random() < epsilon:
        return random.choice(range(len(Q[state])))
    return max(range(len(Q[state])), key=lambda a: Q[state][a])

Q-learning is an off-policy TD method. After taking action a in state s, observing reward r and next state s', it updates: Q(s,a) ← Q(s,a) + α[r + γ max_{a'} Q(s',a') − Q(s,a)]. The target r + γ max Q(s',a') uses the greedy next action, regardless of what the behavior policy actually does. This makes Q-learning off-policy. With enough exploration and a decaying learning rate, Q(s,a) converges to Q*(s,a).

# Q-learning update
Q[s][a] += alpha * (r + gamma * max(Q[s_next]) - Q[s][a])

Both are TD methods, but they differ in the target used for updating Q(s,a). Q-learning uses the max over next actions: target = r + γ max_{a'} Q(s',a') — making it off-policy. SARSA uses the actual next action taken: target = r + γ Q(s', a') — making it on-policy. SARSA is safer in environments with cliffs or penalties because it accounts for the exploration policy. Q-learning is more aggressive and can learn faster in benign settings.

# SARSA update
Q[s][a] += alpha * (r + gamma * Q[s_next][a_next] - Q[s][a])

γ ∈ [0,1] controls how much the agent values future rewards relative to immediate ones. With γ=0 the agent is purely myopic (only cares about immediate reward). With γ close to 1 the agent values long-term rewards nearly as much as immediate ones. γ also ensures the infinite sum of rewards converges: G_t = Σ_{k=0}^∞ γ^k r_{t+k}. Choosing γ is a design decision: low γ for short-horizon tasks, high γ for long-horizon planning.

TD learning updates value estimates using bootstrapping — it updates based on the current estimate of the next state rather than waiting for the actual episode return. The TD(0) update is: V(s) ← V(s) + α[r + γ V(s') − V(s)]. The term in brackets is the TD error δ = r + γ V(s') − V(s). TD combines ideas from Monte Carlo (learning from experience) and dynamic programming (bootstrapping), and can learn online without waiting for episode end.

# TD(0) update
V[s] += alpha * (r + gamma * V[s_next] - V[s])

Monte Carlo (MC) methods update value estimates only at the end of an episode, using the actual total return G_t = Σ γ^k r_{t+k}. This gives unbiased but high-variance estimates. TD learning updates at every step using bootstrapped estimates — lower variance but biased. MC works only for episodic tasks; TD can handle continuing tasks. In practice, TD(λ) interpolates between them using eligibility traces, giving a family of methods between MC (λ=1) and TD(0) (λ=0).

REINFORCE is the foundational policy gradient algorithm. It directly optimizes the policy by gradient ascent on expected return. The gradient estimate is: ∇J(θ) ≈ Σ_t G_t ∇ log π_θ(a_t|s_t). This uses the log-derivative trick. Actions that led to high returns get their probability increased; low-return actions get decreased. REINFORCE is unbiased but has high variance, often mitigated by subtracting a baseline b(s) from G_t, giving the advantage A_t = G_t − b(s_t).

# REINFORCE gradient (pseudocode)
loss = -sum(G_t * log_prob(a_t) for t in trajectory)

Actor-critic combines policy gradient (actor) with value function estimation (critic). The actor π_θ(a|s) selects actions; the critic V_w(s) estimates state values. The actor is updated using the advantage A_t = r + γ V(s') − V(s) instead of raw returns, reducing variance. The critic is updated by minimizing TD error. This combination is more stable than pure policy gradient (lower variance) and more data-efficient than pure value-based methods. A2C and A3C are popular actor-critic variants.

DQN extends Q-learning to high-dimensional state spaces (e.g., Atari pixels) using a neural network to approximate Q(s,a;θ). Two key stabilization tricks: (1) Experience replay — store transitions in a replay buffer and sample random mini-batches, breaking temporal correlations. (2) Target network — use a separate, slowly updated network Q(s,a;θ⁻) for computing TD targets, preventing moving-target instability. Together these allow stable training of deep Q-networks on complex tasks.

The multi-armed bandit is a simplified RL problem: no states, just actions (arms). Each arm gives a stochastic reward from an unknown distribution. The goal is to maximize total reward by balancing exploration (trying arms to estimate their values) and exploitation (pulling the arm with the highest estimated value). It's a pure exploration-exploitation trade-off. Strategies include ε-greedy, UCB (Upper Confidence Bound), and Thompson Sampling. Bandits model A/B testing, ad selection, and clinical trials.

On-policy methods learn the value of the policy currently used to generate data (e.g., SARSA). Off-policy methods learn about a target policy while following a different behavior policy (e.g., Q-learning learns the greedy policy while ε-greedy is used for exploration). Off-policy is more data-efficient (can reuse old data) but harder to stabilize. On-policy is simpler but requires fresh data whenever the policy changes. DQN is off-policy; PPO is on-policy.

Reward shaping adds auxiliary rewards to the environment signal to guide learning faster: R'(s,a,s') = R(s,a,s') + F(s,s'). The risk is reward hacking — the agent may exploit the shaped signal without achieving the true goal. Potential-based shaping F(s,s') = γΦ(s') − Φ(s) is provably safe: it preserves the optimal policy of the original MDP. Poor shaping can create unintended behaviors, like an agent spinning in circles to collect shaped rewards instead of completing the task.

Value iteration is a dynamic programming algorithm. It iteratively applies the Bellman optimality equation: V_{k+1}(s) = max_a Σ P(s'|s,a)[R(s,a) + γ V_k(s')]. Starting from arbitrary V_0, it converges to V* as k→∞. Once V* is found, the optimal policy is: π*(s) = argmax_a Σ P(s'|s,a)[R(s,a) + γ V*(s')]. Value iteration requires the full model P(s'|s,a), so it is model-based. Q-learning approximates this model-free using sampled transitions.

PPO is a popular on-policy policy gradient algorithm that constrains how much the policy changes per update. It clips the probability ratio r_t(θ) = π_θ(a|s) / π_{θ_old}(a|s) within [1−ε, 1+ε], preventing destructively large updates. The clipped objective is: L = E[min(r_t A_t, clip(r_t, 1−ε, 1+ε) A_t)]. PPO is simpler than TRPO (no second-order optimization) but achieves similar stability and is widely used for training LLMs via RLHF.

The replay buffer stores past transitions (s, a, r, s') and allows random mini-batch sampling during training. This breaks temporal correlation between consecutive samples (which would violate the i.i.d. assumption of SGD) and allows data reuse across many gradient updates. Without it, the network trains on highly correlated sequential data, leading to unstable or oscillating Q-values. The buffer typically holds 10^4–10^6 transitions. Prioritized experience replay further improves efficiency by sampling high-TD-error transitions more often.

The advantage function measures how much better action a is compared to the average action in state s: A(s,a) = Q(s,a) − V(s). A positive advantage means the action is better than average; negative means worse. Using advantages instead of raw Q-values in policy gradient reduces variance because V(s) acts as a baseline. In actor-critic methods, A(s,a) ≈ r + γ V(s') − V(s) (the TD error), which can be estimated without computing Q explicitly.

# Advantage estimate
advantage = r + gamma * V(s_next) - V(s)

Model-free RL learns directly from environment interactions without learning the transition dynamics P(s'|s,a). Examples: Q-learning, PPO. Model-based RL first learns a model of the environment, then uses it for planning (e.g., via simulated rollouts). Model-based methods are more sample-efficient but suffer if the learned model is inaccurate. Dyna-Q combines both: it learns Q-values from real experience AND simulated experience generated by a learned model, getting benefits of both approaches.

UCB selects the action with the highest upper confidence bound: a_t = argmax_a [Q(a) + c√(ln t / N(a))]. The first term exploits the best-known action; the second term encourages exploring less-tried actions (small N(a)) as time grows. The constant c controls exploration strength. UCB is deterministic and provably achieves near-optimal cumulative regret of O(ln T). Unlike ε-greedy, UCB focuses exploration on uncertain actions rather than uniform random selection.

import numpy as np
def ucb(Q, N, t, c=2):
    return np.argmax(Q + c * np.sqrt(np.log(t+1) / (N + 1e-8)))

Sparse reward means the agent only receives meaningful reward rarely (e.g., winning a game). This makes learning extremely slow because most trajectories give zero gradient signal. Solutions include: (1) Reward shaping to add dense intermediate rewards. (2) Hindsight Experience Replay (HER) — replay failed trajectories as if the achieved state was the goal. (3) Curiosity-driven exploration with intrinsic rewards based on prediction error. (4) Curriculum learning — start with easier tasks and gradually increase difficulty.

The policy gradient theorem gives the gradient of expected return with respect to policy parameters θ: ∇_θ J(θ) = E_{π_θ}[∇_θ log π_θ(a|s) · Q^{π_θ}(s,a)]. This result is powerful because it doesn't require differentiating through the environment dynamics P(s'|s,a). The log-derivative trick turns the gradient of π into an expectation computable from rollouts. This forms the basis of REINFORCE, actor-critic, PPO, and nearly all modern deep RL policy optimization.

Episodic tasks have a natural endpoint (terminal state) after which the agent resets — e.g., playing a game, navigating a maze. The return is well-defined: G_t = Σ_{k=0}^T γ^k r_{t+k}. Continuing tasks have no terminal state — e.g., a robot running indefinitely. For continuing tasks, undiscounted returns diverge, so γ < 1 is essential, or the objective is reformulated as average reward per time step. Many real-world RL problems are framed as episodic for tractability.

Eligibility traces give credit to recently visited state-action pairs for current rewards, enabling multi-step credit assignment. TD(λ) interpolates between TD(0) (λ=0, one-step bootstrap) and Monte Carlo (λ=1, full return). The λ-return G_t^λ = (1−λ) Σ_{n=1}^∞ λ^{n-1} G_t^{(n)} blends n-step returns. The eligibility trace e(s) tracks how recently and frequently each state was visited. TD(λ) often learns faster than pure TD or MC in practice.

The policy improvement theorem guarantees that if we act greedily with respect to the value function of policy π to get π', then V^{π'}(s) ≥ V^π(s) for all states s. In other words, a greedy policy improvement step never makes the policy worse. This is the foundation of policy iteration: alternate between policy evaluation (compute V^π) and policy improvement (greedy update). The algorithm converges to the optimal policy π* in a finite number of iterations for finite MDPs.

Standard DQN suffers from overestimation bias: using max_a Q(s',a;θ) for both action selection and evaluation inflates Q-values. Double DQN decouples these: use the online network θ to select the best action, but use the target network θ⁻ to evaluate it: target = r + γ Q(s', argmax_a Q(s',a;θ); θ⁻). This reduces overestimation, leading to more accurate Q-values and better performance. Double DQN consistently outperforms vanilla DQN on Atari benchmarks.

# Double DQN target
a_best = online_net(s_next).argmax()
target = r + gamma * target_net(s_next)[a_best]

Credit assignment is the challenge of determining which past actions caused a delayed reward. If an agent wins a game after 100 steps, which of those steps were actually responsible? Temporal credit assignment across time is hard. Solutions include eligibility traces (recent actions get more credit), Monte Carlo returns (propagate full return backwards), and n-step returns. Structural credit assignment across network components is addressed by backpropagation. This is a core challenge distinguishing RL from supervised learning.

Dueling DQN splits the Q-network into two streams: one estimating the state value V(s) and another estimating the advantage A(s,a) = Q(s,a) − V(s). They are combined as Q(s,a) = V(s) + (A(s,a) − mean_a A(s,a)), subtracting the mean advantage for identifiability. This architecture helps because many states have similar value regardless of action taken — learning V(s) separately is more data-efficient. Dueling DQN improves upon vanilla DQN especially when many actions have similar Q-values.

A Markov chain is a stochastic process over states where transitions P(s'|s) depend only on the current state (no actions or rewards). An MDP extends it by adding actions and rewards: the agent influences state transitions through action choice and receives rewards. A Markov chain models passive dynamics; an MDP models active decision-making. Every MDP reduces to a Markov chain once the policy is fixed: the policy + MDP = Markov reward process, where transitions follow π's decisions.

TRPO constrains policy updates to a trust region using the KL divergence between old and new policies: max E[π_θ(a|s)/π_{θ_old}(a|s) · A(s,a)] subject to E[KL(π_{θ_old}||π_θ)] ≤ δ. This prevents destructively large policy updates that collapse performance. TRPO uses conjugate gradient and line search to solve the constrained optimization efficiently. PPO approximates TRPO's constraint with a simpler clipping mechanism, achieving similar performance with much lower implementation complexity.

SARSA (State-Action-Reward-State-Action) updates: Q(s,a) ← Q(s,a) + α[r + γ Q(s',a') − Q(s,a)], where a' is the actual next action taken by the policy. Because it uses the real next action rather than the greedy max, SARSA is on-policy. In Cliff-Walking, SARSA learns a safe path away from edges (because it accounts for occasional ε-random steps near cliffs), while Q-learning learns the shortest but riskier edge path.

In model-based RL, the agent learns a model M: (s,a) → (s', r), then plans using this model. Planning uses the model to look ahead (e.g., tree search, value iteration on the learned model) without further environment interaction. Learning updates parameters from data. Dyna-Q alternates: it learns from real experience AND plans using the learned model via simulated rollouts. AlphaGo/AlphaZero use MCTS planning with a learned value/policy network for board games.

Intrinsic motivation augments the extrinsic reward with internal curiosity signals, helping agents explore in sparse-reward environments. Common forms: prediction error (high surprise = high reward), novelty (reward for visiting rare states), and count-based exploration. Random Network Distillation (RND) gives intrinsic reward proportional to how surprising a state is to a randomly initialized neural network. Intrinsic rewards allow agents to master hard games like Montezuma's Revenge that stumped extrinsic-only agents.

A deterministic policy π(s) = a always selects the same action in a given state. A stochastic policy π(a|s) outputs a probability distribution over actions. Stochastic policies are essential in: (1) Partially observable environments where randomization can be optimal. (2) Game-theoretic settings where predictability is exploitable. (3) Policy gradient methods that require the policy to be differentiable. Deterministic policies (used in DDPG) work well in continuous action spaces where the gradient of Q(s,π(s)) w.r.t. π is well-defined.

DDPG extends DQN to continuous action spaces. It uses a deterministic actor μ_θ(s) that directly outputs the action, and a critic Q_w(s,a) that evaluates it. The actor is updated by gradient ascent on Q: ∇_θ J ≈ E[∇_a Q_w(s,a)|_{a=μ_θ(s)} · ∇_θ μ_θ(s)]. DDPG also uses experience replay and target networks from DQN. It's off-policy and sample-efficient. SAC (Soft Actor-Critic) extends DDPG with entropy regularization for better exploration.

Entropy regularization adds a bonus for high-entropy (exploratory) policies to the RL objective: J(θ) = E[Σ_t γ^t(r_t + α H(π(·|s_t)))], where H is the policy entropy. This discourages premature convergence to deterministic policies and encourages exploring all viable options. The temperature α controls exploration-exploitation trade-off. Soft Actor-Critic (SAC) uses this framework, automatically tuning α. Entropy regularization also appears in RLHF for LLM alignment, preventing the policy from collapsing to single outputs.

GAE smoothly interpolates between 1-step TD (low variance, high bias) and Monte Carlo (high variance, low bias) for advantage estimates: A_t^{GAE(γ,λ)} = Σ_{l=0}^∞ (γλ)^l δ_{t+l}, where δ_t = r_t + γV(s_{t+1}) − V(s_t) is the TD error. With λ=0, GAE = 1-step TD error; with λ=1, GAE = discounted sum of TD errors = MC advantage. PPO combines GAE for advantage estimation with clipped policy updates, forming the most widely used RL algorithm for complex tasks.

The target network is a copy of the Q-network whose weights θ⁻ are updated slowly (either periodically copied from the online network or soft-updated: θ⁻ ← τθ + (1−τ)θ⁻). It computes stable TD targets: y = r + γ max_a Q(s',a;θ⁻). Without it, the target moves every gradient step — the network is chasing a moving target, causing oscillations or divergence. The target network breaks this feedback loop, stabilizing training at the cost of slightly stale targets.

# Soft update
for p, p_target in zip(net.parameters(), target.parameters()):
    p_target.data = tau*p.data + (1-tau)*p_target.data

Reward clipping clips all rewards to the range [−1, +1] (or [0, 1]). In DQN applied to Atari, different games have very different reward scales (scores of 1 vs. 10,000). Clipping normalizes rewards so the same hyperparameters (learning rate, Q-value scale) work across games. The downside is loss of magnitude information — the agent can't distinguish +1 from +1,000. Reward normalization (divide by running std) is a softer alternative that preserves ordering without discarding magnitude entirely.

reward = np.clip(reward, -1, 1)

HER addresses sparse goal-conditioned reward by replaying failed trajectories as if a different goal had been intended. After a failed episode reaching state s_T instead of goal g, HER adds replay transitions with goal g' = s_T, giving reward +1 retroactively. This turns every episode into a learning signal regardless of success. HER dramatically accelerates learning in robotic manipulation and navigation tasks with sparse binary rewards. It is compatible with any off-policy algorithm like DDPG or SAC.

Value-based methods (Q-learning, DQN) learn a value function and derive the policy implicitly (e.g., greedy w.r.t. Q). They work well for discrete action spaces but struggle in continuous ones. Policy-based methods (REINFORCE, PPO) directly parameterize and optimize the policy, handling continuous actions naturally and learning stochastic policies. Actor-critic methods combine both: a policy network (actor) and a value network (critic). Value-based methods tend to be more sample-efficient; policy-based are more stable in complex environments.

The Bellman optimality equation for Q* is: Q*(s,a) = Σ_{s'} P(s'|s,a)[R(s,a,s') + γ max_{a'} Q*(s',a')]. It says the optimal Q-value of (s,a) equals the expected immediate reward plus the discounted value of the best action in the next state. The optimal policy is then π*(s) = argmax_a Q*(s,a). Q-learning approximates this equation by using samples instead of the true transition probabilities, updating Q iteratively toward Q*.

A3C (Asynchronous Advantage Actor-Critic) runs multiple workers asynchronously, each interacting with its own environment copy and sending asynchronous gradient updates to a shared network. A2C (Advantage Actor-Critic) is the synchronous version — all workers complete their rollouts, then gradients are averaged and applied together. A2C is easier to implement and more reproducible; A3C can be faster on CPU. Both use advantage estimates to reduce variance. A2C with GPU batching often matches A3C performance with less engineering complexity.

The exploration-exploitation dilemma is the fundamental trade-off in RL: should the agent try new actions to discover potentially better rewards (explore) or stick with actions known to be good (exploit)? Pure exploitation misses better options; pure exploration never uses what was learned. The optimal balance depends on how much time remains and how uncertain current estimates are. This trade-off appears everywhere: A/B testing, recommendation systems, clinical trials, and hyperparameter search, not just RL.

Thompson Sampling is a Bayesian exploration strategy for bandits. It maintains a prior distribution over each arm's reward parameter, samples one value from each posterior, then pulls the arm with the highest sample. After observing the reward, it updates the posteriors. For Bernoulli bandits with Beta priors, this is: sample θ_a ~ Beta(α_a, β_a), pull argmax θ_a, update α or β based on success/failure. Thompson Sampling achieves near-optimal regret and often outperforms UCB in practice due to automatic uncertainty calibration.

import numpy as np
def thompson(alphas, betas):
    samples = np.random.beta(alphas, betas)
    return np.argmax(samples)

A Partially Observable MDP (POMDP) is an MDP where the agent cannot directly observe the true state s — it only sees observations o ~ O(o|s). The agent must maintain a belief state b(s) = P(s|o_{1:t}, a_{1:t-1}) representing uncertainty over states. Optimal POMDP policies map belief states to actions. Solutions include QMDP, PBVI, or simply using recurrent policies (LSTM) that implicitly track belief from observation history. POMDPs model robots with noisy sensors, card games (hidden hands), and real-world perception tasks.

Reward is the scalar signal the agent receives after each action, indicating immediate desirability. Good reward design: (1) Be truthful — reflect the true objective, not a proxy. (2) Be timely — dense rewards near the goal help credit assignment. (3) Avoid reward hacking — ensure the agent can't exploit the signal without achieving the goal. Bad examples: rewarding survival in an escape task causes the agent to avoid escaping. Reward design is often the hardest part of applying RL to real problems.

Tabular RL stores exact values for each (s,a) pair in a table — practical only for small, discrete state spaces. Function approximation replaces the table with a parameterized function (e.g., neural network): Q(s,a;θ). This generalizes across similar states, enabling RL in continuous or high-dimensional spaces like images. However, function approximation can cause instability (deadly triad: off-policy + bootstrapping + function approximation). DQN addresses this with replay buffer and target networks.

Multi-agent RL (MARL) involves multiple agents interacting in a shared environment, each learning its own policy. Agents can be cooperative (maximize shared reward), competitive (zero-sum), or mixed. Challenges include non-stationarity (each agent's optimal policy depends on others' changing policies), scalability, and credit assignment in cooperative settings. CTDE (Centralized Training, Decentralized Execution) is a popular paradigm: agents train with full information but execute with only local observations. Examples: QMIX, MADDPG, AlphaStar.