Skip to content

rl.md

Latest commit

 

History

History
160 lines (113 loc) · 17.7 KB

rl.md

File metadata and controls

160 lines (113 loc) · 17.7 KB
Raw

Reinforcement learning

RL vs supervised learning

  • Reinforcement learning is teaching by experience: the agent tries actions, observes outcomes, and learns from reward signals. No one tells the agent the correct action - it must discover which actions yield the most reward through trial and error.
  • Supervised learning is teaching by example: the model is shown labeled examples of correct answers and learns to imitate them.

Supervised learning minimizes a loss function against known correct answers, whereas RL maximizes expected cumulative reward without ever being told the correct action.

In practice, deep RL code still minimizes. Optimizers such as SGD and Adam only descend, so policy gradient methods negate the objective and minimize $-\mathbb{E}[G]$. The training loop looks the same as in supervised learning: compute the loss, call loss.backward(), and step the optimizer. Value-based methods like DQN minimize a regression loss on the TD error instead of a negated reward. Either way, the minus sign or the regression target is an implementation detail. The goal is still to maximize return.

RL is fundamentally about making a sequence of decisions, not a single prediction. Each action changes the state of the environment, which affects what actions and rewards are available later. Rewards may be delayed - a chess move may only pay off many moves later - so the agent must learn which earlier decisions deserve credit for eventual outcomes (the credit assignment problem). This sequential, delayed-feedback structure is what distinguishes RL from supervised learning, where each prediction is independent and feedback is immediate.

Imitation learning sits between supervised and rl: the agent learns from expert demonstrations rather than reward. Behavioral cloning is the simplest form — plain supervised learning on (state, expert action) pairs. Its weakness is compounding error: once the agent drifts into a state the expert never visited, it has no idea what to do, and the mistake grows. Inverse RL instead infers the reward function the expert appears to be optimizing, then runs normal RL on it.

Real-world RL applications

  • Game Playing: Beating world champions in complex board games (Go, Chess) and real-time strategy video games (Dota 2, StarCraft II).
  • Robotics: Training robotic arms to grasp objects, or teaching quadrupedal robots to walk over uneven terrain.
  • Autonomous Driving: Optimizing trajectory planning, lane-changing behavior, and collision avoidance systems.
  • Advertising: Real-time bid optimization in ad auctions, budget pacing across campaigns, and sequential ad selection that maximizes long-term conversions instead of immediate clicks.
  • Large Language Models (LLMs): Fine-tuning models using RLHF (Reinforcement Learning from Human Feedback) to ensure AI responses align with human preferences regarding safety and helpfulness.

RL Terminology

An agent interacts with an environment and learns to take action by maximizing an expected cumulative reward.

  • Agent: The AI system, decision-maker, or learner (e.g., a self-driving car software or a chess-playing bot).
  • Environment: Everything outside the agent that it interacts with (e.g., the physical roads or the chessboard).
  • State ($s$): The current situation or configuration of the environment at a specific time.
  • Action ($a$): The choices available to the agent (e.g., turn left, move pawn to E4).
  • Reward ($r$): The feedback signal from the environment evaluating the agent's last action. It is a function of the state and action, $r(s, a)$ — the same action can be good in one state and bad in another. Rewards can be positive (a reward) or negative (a penalty). Examples include:
    • Games: win, maximize score
    • Finance: gains, gains minus risk
    • Drone delivery: positive delivery reward, penalty for collision.
345fadfa-549a-462a-b757-9ab258e747f3

  • Observation (O) The information the agent receives from the environment at each step. If the observation captures the complete state, the environment is fully observable (like a chessboard); if not, it is partially observable (like a poker hand or a car's camera view).

  • Terminal state is one where the episode ends — no further actions or rewards follow. Examples include:

    • Chess or Go: checkmate, resignation, or a draw
    • Robotics: A drone landing at its target — or crashing
    • Finance and wagering: Bankruptcy — bankroll hits zero
    • Finance: An options position expiring
    • A treatment-planning MDP in healthcare: patient recovery or death

  • Trajectory ($\tau$) - the sequence of states, actions, and rewards from one run: $(s_0, a_0, r_0, s_1, a_1, \ldots)$. Also called a rollout when generated by the current policy for training, or an episode when it ends in a terminal state.

Policy

  • Policy ($\pi$): The decision-making rule the agent is learning — a mapping from states to actions. The policy defines the agent's behavior.

    • A deterministic policy returns a single action for each state: $A = \pi(S)$.
    • A stochastic policy returns a probability distribution over actions: $\pi(A|S)$.

  • In small, tractable problems the policy can be derived from a Q-table — a lookup table storing an estimated value for every state-action pair, where the agent simply picks the action with the highest value. In complex problems the state space is too large to enumerate, so the mapping is approximated with a neural network (the "deep" in deep RL).

Markov Decision Process (MDP)

A Markov Decision Process is the formal framework for sequential decision making under uncertainty. Nearly all RL theory assumes the problem is an MDP.

The Markov property is the defining assumption: the next state and reward depend only on the current state and action, not on the history that led there. The state is a sufficient statistic for the future.

  • Chess satisfies it — the board position (plus castling/en passant flags) is all you need; how you arrived is irrelevant.
  • A single Atari frame does not — you can't tell which way the ball is moving. Stacking four frames restores it.

POMDP

A partially observable MDP (POMDP) is the generalization where the agent can't see the full state, only an observation of it. Poker (hidden cards), a robot with a limited camera view, and a race where fitness and intent aren't in the data are all POMDPs. The standard workaround is to make the observation more Markov — stack recent frames, or carry history in a recurrent or attention-based network — so the agent's internal representation approximates the state it can't see.

Return and value functions

The agent maximizes the return ($G$) — the discounted sum of all future rewards from a point onward, not the immediate reward. Discounting by $\gamma$ (0 to 1) keeps the sum finite and weights sooner rewards more heavily.

$$G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \ldots = \sum_{k=0}^{\infty} \gamma^k r_{t+k}$$

A value function is the expected return — an average over the many ways the future could unfold, since both the environment and the policy are stochastic. Values are always relative to a policy: a state is only as good as what the agent does from there.

  • State-value $V^\pi(s)$ — the expected return from state $s$ following policy $\pi$. "How good is it to be here?"
  • Action-value $Q^\pi(s, a)$ — the expected return from taking action $a$ in state $s$, then following $\pi$. "How good is this move from here?"

Q is the more directly useful of the two for choosing actions: given Q, the policy is simply $\arg\max_a Q(s,a)$ — no model of the environment required. This is what a Q-table stores and what the "Q" in Q-learning and DQN refers to.

The goal of RL is to find the optimal policy $\pi^*$ — the one maximizing expected return:

$$\pi^* = \arg\max_\pi \mathbb{E}_\pi\left[\sum_{t=0}^{\infty} \gamma^t r_t\right]$$

The expectation matters: outcomes are stochastic, so the agent maximizes the average return over many possible futures, not the return of any single run. The subscript $\pi$ is the subtle part — the policy determines which trajectories you experience, so changing the policy changes the distribution you're averaging over. That circularity is what makes RL harder than supervised learning, where the data distribution is fixed.

The Bellman Equation

The Bellman equation expresses the core recursive idea of RL: the value of where you are now = the reward you get now + the value of where you end up next.

  • Instead of evaluating a state by playing out an entire episode, the agent can break the problem into one step at a time: take an action, collect the immediate reward, and rely on its estimate of the next state's value to account for everything after that.
  • Future rewards are typically discounted by a factor 𝛾 (gamma, between 0 and 1), meaning a reward now is worth slightly more than the same reward later. This keeps values finite and makes the agent prefer faster paths to reward.
  • This recursive structure is what makes learning practical: the agent doesn't need to see the end of the game to update its estimates — it can bootstrap, improving its value estimate for the current state using its estimate of the next one. Q-learning and DQN are built directly on this idea.

Exploration vs exploitation

The agent faces a constant dilemma: exploit the best action it currently knows, or explore other actions that might be better. Pure exploitation gets stuck on the first decent strategy found; pure exploration never cashes in on what's been learned.

  • ε-greedy is the simplest solution: act greedily, but with probability ε (e.g. 0.1) pick a random action instead. ε is typically annealed from high to low over training explore early, exploit late.
  • Stochastic policies explore naturally by sampling from π(A∣S); an entropy bonus in the loss keeps the distribution from collapsing prematurely.
  • The multi-armed bandit is the minimal version of the problem — one state, many actions, which slot machine do you pull? — and the setting where the tradeoff was first studied.

Reward design

The reward function is the only way to tell the agent what you want, and the agent optimizes exactly what you specify, not what you meant.

Reward shaping

Many natural rewards are sparse: a robot gets +1 only when the object is grasped, a chess agent only at checkmate. With sparse rewards, random exploration may never stumble onto a reward, so there is nothing to learn from. Reward shaping adds intermediate rewards to guide learning, e.g. a small reward for moving the gripper closer to the object.

  • The risk is that shaped rewards change the optimal policy, so the agent learns to farm the bonus instead of solving the task.
  • Potential-based shaping (Ng, Harada & Russell, 1999) avoids this. Adding $F(s, s') = \gamma \Phi(s') - \Phi(s)$ for any potential function $\Phi$ provably leaves the optimal policy unchanged. The bonuses telescope, so the agent can't gain by cycling.

Reward hacking

Reward hacking (or specification gaming) is when the agent finds a way to score highly on the reward without doing the intended task. It is Goodhart's law applied to RL: when a measure becomes a target, it ceases to be a good measure.

  • CoastRunners (OpenAI, 2016): a boat-racing agent rewarded for hitting score targets learned to circle a lagoon, repeatedly hitting the same respawning targets, catching fire, and never finishing the race, while outscoring human players.
  • RLHF: the reward model is itself a learned approximation of human preference, so the policy can exploit its blind spots. Typical results are longer responses, confident tone, and sycophancy that the reward model scores well but humans don't actually prefer. Pushing optimization further makes true quality peak and then decline, which is called reward model overoptimization.
  • Mitigations: a KL penalty keeping the policy close to the reference model (standard in RLHF), reward model ensembles, periodically retraining the reward model on new policy outputs, and inspecting rollouts rather than trusting the reward curve.

Categories of RL agents

RL algorithms differ in what the agent learns:

  • Value-based: The agent learns a value function (like a Q-table or DQN) and derives its policy implicitly by picking the highest-value action. Examples: Q-learning, DQN.
  • Policy-based: The agent learns the policy directly, optimizing the parameters of $\pi(A|S)$ to maximize expected reward without ever estimating state values. Examples: REINFORCE.
  • Actor-critic: A hybrid — the actor learns the policy while the critic learns a value function that evaluates the actor's actions, reducing the variance of policy updates. Examples: A2C, PPO.

A separate axis is whether the agent models the environment:

  • Model-free: The agent learns purely from experience, with no model of how the environment transitions between states. Most deep RL (DQN, PPO) is model-free.
  • Model-based: The agent learns or is given a model of the environment's dynamics and can plan by simulating outcomes before acting. Example: AlphaZero, which uses tree search over a learned model.

A third axis is how the agent represents what it learns:

  • Tabular RL: Values (or the policy) are stored in a lookup table with one entry per state or state-action pair, like a Q-table. This works only when the state space is small enough to enumerate, such as gridworlds or tic-tac-toe. Tabular methods are easy to reason about and come with convergence guarantees, which is why RL theory and textbooks start there.
  • Deep RL: A neural network approximates the value function or policy, so it can handle huge or continuous state spaces like raw pixels, board positions in Go, or text. The network generalizes across similar states it has never seen, which a table cannot do. The cost is stability: combining function approximation, bootstrapping, and off-policy data can make training diverge. DQN added experience replay and a target network specifically to tame this.

The core ideas (the Bellman equation, exploration, value vs. policy) are the same in both. Deep RL swaps the table for a function approximator.

A fourth axis is where the training data comes from:

  • Online RL: The agent learns while interacting with the environment, so it can try new actions and see what happens. This is the standard setting for games and simulators.
  • Offline RL (also called batch RL): The agent learns from a fixed dataset of past trajectories collected by some other policy, with no further interaction. This fits domains where exploration is expensive or dangerous, such as learning treatment policies from hospital records or a wagering policy from historical results.

Offline RL has a specific failure mode: distributional shift. The learned policy may favor actions that rarely or never appear in the dataset, and the value estimates for those actions are pure extrapolation, often wildly optimistic. An online agent would try the action and correct itself; an offline agent can't. Offline methods such as CQL and IQL counter this by penalizing or avoiding actions the data doesn't support.

Related but distinct is on-policy vs. off-policy, which describes whether an algorithm can learn from data generated by a different policy:

  • On-policy algorithms (REINFORCE, PPO) need fresh data from the current policy, and discard it after each update.
  • Off-policy algorithms (Q-learning, DQN) can learn from data generated by older or different policies, which is what makes DQN's experience replay possible.

Offline RL is the extreme case of off-policy learning: all the data comes from another policy, and none can be added. But most off-policy algorithms are still run online, with the replay buffer constantly refilled by new interactions.

PPO

PPO (Proximal Policy Optimization) is an actor-critic policy gradient algorithm that improves training stability by clipping each update so the new policy can't move too far from the old one. PPO is the workhorse of RLHF (Reinforcement Learning from Human Feedback): in LLM fine-tuning, the language model is the actor, and responses are scored by a reward model — a network trained on human preference data, where humans compare two model responses and pick the better one (comparisons are used because humans are inconsistent at absolute scoring but reliable at relative judgments).

References

Class