Reinforcement Learning

Definition: A reinforcement learning model works with an agent or actor $X$, on a set of states $(S)$ and actions $(A)$ optimizing for a reward $(r)$.

A policy $(p)$ determines the action $(A)$ in state $(S)$ generating a reward $(r)$. The goal of reinforcement learning is to learn this policy.

Learning from experience

The agent and environment loop above is also the answer to a basic question: where does the training signal come from? Unlike supervised learning, reinforcement learning has no fixed dataset of correct answers to train on. The agent has to generate its own data by acting, observing what happens, and gradually shaping a policy from that stream of experience rather than from labeled examples.

Each pass through the loop produces a transition: a state, an action, the reward received, and the next state. A trajectory is just a sequence of these transitions collected over an episode. The return $G_t$ at time $t$ is the discounted sum of future rewards:

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

The discount factor $\gamma \in [0, 1)$ controls how much the agent should weigh a reward now against a similar reward several steps away, and keeps the sum finite in tasks that never end.

A value function is how an agent turns raw experience into an estimate it can act on. The state value $V(s)$ is the expected return starting from state $s$ and following policy $p$ from then on; the action value $Q(s, a)$ does the same but for taking a specific action $a$ in state $s$ first. Both satisfy a Bellman equation, which says a value is just the immediate reward plus the discounted value of wherever the agent ends up next:

$$Q(s, a) = \mathbb{E}\big[r + \gamma \max_{a'} Q(s', a') \mid s, a\big]$$

This recursive structure is what lets an agent learn from a single step of experience rather than waiting for an entire trajectory to finish. Temporal difference (TD) learning updates $Q(s,a)$ toward $r + \gamma \max_{a'} Q(s', a')$ after every step; Monte Carlo methods instead wait until an episode ends and update toward the actual observed return $G_t$. TD learning is the more sample efficient of the two since it bootstraps off its own estimates, and it is the mechanism behind Q-learning and SARSA.

Learning from experience only works if the agent generates experience worth learning from. An agent that always exploits its current best guess never discovers a better one; an agent that always explores never uses what it already knows. This is the exploration and exploitation tradeoff, usually handled with something like an epsilon greedy policy, acting randomly some small fraction of the time, or by adding a bonus reward for visiting unfamiliar states.

Because experience is expensive to collect in the real world, algorithms like DQN reuse it: transitions are stored in a replay buffer and sampled repeatedly during training instead of being used once and discarded. This turns a single trajectory into many gradient updates and is a large part of why deep reinforcement learning became sample efficient enough to work at all. Offline RL takes this idea to its limit and learns an entire policy from a fixed buffer of past experience with no further interaction with the environment.

RL algorithms have enjoyed a great deal of success in games such as atari, chess or go. In such games we have a well defined state, in the real world a context $(C)$ is associated to the state which bundles relevant information to determine a policy. The set of states and actions is well defined and stationary over time. However, in the real world there are a few issues reinforcement learning has to deal with.

Common issues faced in reinforcement learning are listed in (Dulac-Arnold, Mankowitz and Hester, 2019)

Non-stationarity of real world - a lot of the world changes over time. Such changes cause issues with a learnt policy.
Partial observability of state/context - a newly discovered state requries learning the actions and rewards in the state.
The reward can be delayed or partially observable in some states.
A memory problem - without access to the full history, an agent often needs some form of memory to act well in a partially observable environment. In poker, the optimal action depends on cards folded three rounds ago, not just the current hand; recurrent architectures (LSTMs, GRUs) or an explicit memory module are the usual fix, as in DeepMind's Deep Recurrent Q-Network for partially observable Atari games.
A stochastic problem - the same action taken from the same state doesn't always lead to the same outcome. OpenAI Gym's FrozenLake environment makes this explicit: the "slippery" variant only executes the intended move some of the time, sending the agent in a random adjacent direction the rest. A policy has to optimize for expected reward across this uncertainty rather than a single deterministic trajectory.

Types of reinforcement learning:

Model-free reinforcement learning learns a policy or value function purely from interaction with the environment, without ever learning how the environment itself works. Q-learning and its deep learning descendant DQN (which learned to play Atari games directly from pixels) are model-free, as are policy-gradient methods like REINFORCE and actor-critic methods like A3C.
Model-based reinforcement learning first learns (or is given) a model of the environment's dynamics, how states transition and rewards are generated, and uses that model to plan ahead. AlphaZero simulates thousands of future board positions with Monte Carlo tree search before committing to a move; MuZero goes further and learns the model itself rather than being handed the rules of the game.
Off-policy methods can learn the optimal policy from data generated by a different, possibly much older, policy. This is what lets DQN's experience replay buffer keep training on transitions collected thousands of steps ago, and it's the basis of offline RL, which learns entirely from a fixed dataset with no live environment at all.
On-policy methods only learn from data generated by the current policy. SARSA and PPO fall here: every time the policy changes, the data has to be collected again, which is less sample efficient but keeps training stable, part of why PPO became the default for RLHF style fine tuning of language models.

Combining these two axes, model-free vs. model-based, and on-policy vs. off-policy, accounts for most of the practical toolkit: DQN is model-free and off-policy, PPO is model-free and on-policy, and AlphaZero's tree search makes it model-based. Which combination wins depends on how expensive the real world is to interact with: the more costly or irreversible each action is (a robot arm, a chip design, a real customer) the more attractive it becomes to build a model and plan inside it rather than learn purely by trial and error.

References

Dulac-Arnold, G., Mankowitz, D. and Hester, T., 2019. Challenges of real-world reinforcement learning. arXiv preprint arXiv:1904.12901. Available at: <https://arxiv.org/pdf/1904.12901>.

Back to posts