Paper Map

In one sentence: this page is the "world map" of the RL literature — it lays out seventy years of landmark papers along six branches (dynamic programming, tabular methods, policy gradients, deep RL, RLHF, and multi-agent), each with a one-line positioning. It's built for anyone who wants a global coordinate system, is writing a literature review, or needs to answer "which lineage does this new paper belong to?" By the end, you'll be able to say, for any RL paper, which branch it grew out of.

A map differs from a reading list in a crucial way: a reading list tells you what to read, while a map tells you how the papers are related by blood. Once you see the lineage, you realize that seemingly unrelated papers are the same idea reinvented under different conditions — PPO and DQN, for instance, share a common ancestry (both start from the Bellman equation), and so do RLHF and Q-learning (both optimize an implicitly defined objective). This page is the thematic complement to the chronological dimension of The Evolution of RL: that page walks through the decades; this one walks through the themes.

The Six Branches at a Glance

              Six branches of RL papers (by intellectual origin)
 ┌──────────────────────────────────────────────────────────────┐
 │  ① Dynamic programming  1957~  Bellman eq., policy iter.     │
 │        │                              "the foundation"       │
 │  ② Tabular methods      1959~  trial & error, TD, Q-learning │
 │        │                              "learning offline"     │
 │  ③ Policy gradients     1992~  REINFORCE, TRPO, PPO          │
 │        │                              "learn the policy"      │
 │  ④ Deep RL              2013~  DQN family, AlphaGo/MuZero    │
 │        │                              "go neural"             │
 │  ⑤ RLHF                 2022~  InstructGPT, DPO              │
 │        │                              "align with humans"     │
 │  ⑥ Multi-agent          2017~  MADDPG, QMIX, MAPPO           │
 │                                      "many learners"         │
 └──────────────────────────────────────────────────────────────┘
 Reading note: ②③④ are the mainstream, ① is the theoretical
 foundation, and ⑤⑥ are branches that sprouted after 2017

Branch	Core question	Landmark papers	Related concept pages
① Dynamic programming	How to act optimally when the model is known	Bellman 1957, Howard 1960	Value Learning
② Tabular methods	How to learn by trial and error when the model is unknown	Samuel 1959, Sutton 1988, Watkins 1992	Value Learning
③ Policy gradients	How to optimize the policy directly	Williams 1992, TRPO, PPO	Policy Gradient
④ Deep RL	Function approximation + large-scale learning	DQN family, AlphaGo, MuZero	Value Learning and Model-Based
⑤ RLHF	How to align a model with human preferences	InstructGPT, DPO	RLHF
⑥ Multi-agent	What happens when many learners coexist	MADDPG, QMIX, MAPPO	Multi-Agent

Below we walk through each branch in turn. Each paper follows this format: paper title (authors, year, journal/conference) — one-line positioning.

The Dynamic Programming Branch: A Theoretical Foundation from 1957

This branch answers the oldest question of all: given a complete model of the world, what is the optimal policy? Its answer — the Bellman equation — became the bedrock of every branch that followed, because all RL algorithms are, at heart, doing the same thing under the handicap of an unknown model: approximating the solution to that equation.

1. Bellman, A Markovian Decision Process (1957, Indiana University Mathematics Journal)

— One-line positioning: Formalized sequential decision-making with delayed rewards as a Markov decision process (MDP) and gave the recursive equation of optimality (the Bellman equation), giving sequential decision problems a unified mathematical language for the first time.

The core equation (the Bellman optimality equation):

V*(s) = max_a Σ_s' P(s'|s,a) [ R(s,a,s') + γ V*(s') ]

Every algorithm in this lineage — value iteration, Q-learning, DQN — can be read as "approximating the solution to this equation under different conditions." See the Value Learning concept page for an intuitive walkthrough of the Bellman equation, and the close reading chapters in Classic Paper Readings.

2. Howard, Dynamic Programming and Markov Processes (1960, MIT Press monograph)

— One-line positioning: Turned "policy iteration" into a computable algorithm (alternating between policy evaluation ↔ policy improvement), transforming dynamic programming from a theoretical equation into an engineering method.

The two-step alternation of policy iteration remains the skeleton of many RL algorithms today:

Policy evaluation: given π, solve the linear system for V^π (or iterate toward it)
   ↓
Policy improvement: π'(s) = argmax_a Σ P(s'|s,a)[R + γ V^π(s')]
   ↓
Repeat until the policy stops changing

The Classic Tabular Branch: From Trial and Error to Off-Policy

This branch asks: no model, only trial-and-error interaction with the environment — how do we learn? It transformed "learning" from a problem in optimal control theory (which needs a model) into genuine machine learning (which learns from experience).

1. Samuel, Some Studies in Machine Learning Using the Game of Checkers (1959, IBM Journal of Research and Development)

— One-line positioning: A checkers program that improved through self-play plus a learned evaluation function — the first successful demonstration of "getting better from experience," decades before the term reinforcement learning was coined.

Two ideas from the Samuel program still live at the frontier: self-play (the direct ancestor of AlphaZero in its ultimate form) and a temporal-difference-flavored value update (adjusting the evaluation function toward the evaluation of the next position — a proto-form of the TD idea).

2. Sutton, Learning to Predict by the Methods of Temporal Differences (1988, Machine Learning 3(1))

— One-line positioning: Introduced temporal-difference (TD) learning — updating an earlier estimate using "the current estimate" (bootstrapping) — and showed on a random-walk prediction task that it converges faster than Monte Carlo.

The TD update (TD(0) form; the TD error is the star of the show):

δ = r + γ V(s') - V(s)          # TD error: actual return minus current estimate
V(s) ← V(s) + α δ                # step in the direction that shrinks the TD error

Why TD can beat MC: MC must wait for an entire trajectory to finish before updating (high variance, low bias), while TD can update at every step (low variance, but biased). This bias-variance trade-off is the recurring theme of the Value Learning page.

3. Watkins, Learning from Delayed Rewards (1989, Cambridge PhD dissertation) + Watkins & Dayan, Q-learning (1992, Machine Learning 8(3))

— One-line positioning: Defined the action value Q(s,a) and the Q-learning update rule, and proved it converges to the optimal Q* in finite MDPs — the starting gun of the off-policy revolution.

Q-learning is one of the most important single-algorithm papers in RL history:

Q(s,a) ← Q(s,a) + α [ r + γ max_a' Q(s',a') - Q(s,a) ]

What off-policy means: the update uses max_a' (the target policy is greedy), while the behavior policy generating the data can be any exploration strategy, such as ε-greedy — learning and acting are decoupled. That is the deepest difference from SARSA (on-policy, introduced by Rummery & Niranjan in 1994). The intuition behind the convergence proof: the Q-update is a stochastic approximation of the Bellman optimality operator, which is a contraction. For the full intuition and the SARSA comparison, see Value Learning.

4. Rummery & Niranjan, On-line Q-learning Using Connectionist Systems (1994, Cambridge technical report CUED/F-INFENG/TR166)

— One-line positioning: Proposed the SARSA update (replacing max with the action actually taken next), the canonical representative of on-policy value learning.

The SARSA update:

Q(s,a) ← Q(s,a) + α [ r + γ Q(s',a') - Q(s,a) ]
   # note: this is not max_a', but the a' the policy would actually take

The on-policy vs. off-policy trade-off is a classic interview question: SARSA is conservative (it learns the consequences of exploring), while Q-learning is optimistic (it assumes everything from here on is greedy). Scenario questions live in the Interview Question Bank.

The Policy Gradient Branch: The Other Great Artery from 1992

The tabular branch learns the value of states and actions; the policy gradient branch learns the policy itself. When the action space is continuous or the state space enormous, the value-based argmax becomes intractable, and optimizing the policy directly is the natural way out.

1. Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning (1992, Machine Learning 8(3))

— One-line positioning: Introduced REINFORCE — updating the policy network by the full-trajectory return times the log-probability gradient of the action — and gave the first general form of the policy gradient.

The REINFORCE update intuition: high return → push up the probability of this action; low return → push it down. It is unbiased, but its variance is enormous — because a full Monte Carlo trajectory return serves as the weight. For the rigorous statement and intuition of the policy gradient theorem, see the Policy Gradient concept page.

2. Sutton, McAllester, Singh, Mansour, Policy Gradient Methods for Reinforcement Learning with Function Approximation (1999, NeurIPS 12)

— One-line positioning: Proved the policy gradient theorem with function approximation (even without a compatible value-function approximation, the gradient direction is still sound), pushing policy gradient methods toward scalability.

The policy gradient theorem (intuition version): the gradient of the policy π's objective J with respect to parameters θ is proportional to "the expectation under the state distribution of: advantage function × log-policy gradient":

∇_θ J(θ) = E[ ∇_θ log π_θ(a|s) · A(s,a) ]

3. Schulman et al., Trust Region Policy Optimization (TRPO, 2015, arXiv:1502.05477)

— One-line positioning: Constrained the step size of each update with a KL-divergence trust region — the first time policy gradients became "safe to take big steps with."

TRPO solves the constrained optimization with second-order methods: stable but complex. Its real contribution is the idea: instead of blindly following the gradient, constrain how far the new policy can drift from the old one. That idea directly begat PPO.

4. Schulman et al., Proximal Policy Optimization Algorithms (PPO, 2017, arXiv:1707.06347)

— One-line positioning: Approximates TRPO's trust region with a first-order clipped objective — stable, simple, and easy to parallelize — becoming the workhorse algorithm for both deep RL and RLHF.

The clipped objective (note it's the ratio r_t(θ), not a parameter-space distance):

L^CLIP(θ) = E_t[ min( r_t(θ) Â_t,  clip(r_t(θ), 1-ε, 1+ε) Â_t ) ]
  where r_t(θ) = π_θ(a_t|s_t) / π_θold(a_t|s_t)

Why it replaced TRPO: the implementation is a few lines, no second derivatives or conjugate gradients are needed, and it's more robust to hyperparameters. A close reading lives in Classic Paper Readings; the mechanics are dissected on the Policy Gradient page.

5. Haarnoja et al., Soft Actor-Critic (SAC, 2018, arXiv:1801.01290)

— One-line positioning: Explicitly maximizes "return + entropy" within the Actor-Critic framework — the de facto standard for continuous control when both sample efficiency and stability matter.

SAC's distinguishing move is writing exploration (entropy) into the objective function instead of relying on ε-greedy or injected noise: J = Σ E[ r + α·H(π(·|s)) ], where α is a (automatically tuned) temperature coefficient. It beat DDPG/TD3 in sample efficiency across the MuJoCo continuous-control suite and became the mainstream choice for robotics tasks. Details on the Actor-Critic Family page.

The Deep RL Branch: Going Neural from 2013

This branch married tabular methods and policy gradients with deep learning — the source of what the general public thinks of as "RL going viral."

1. Mnih et al., Playing Atari with Deep Reinforcement Learning (2013, arXiv:1312.5602) and Human-level control through deep reinforcement learning (2015, Nature 518)

— One-line positioning: DQN learns a Q-function directly from pixels with a CNN, and two key tricks (experience replay + target network) made deep Q-learning stable for the first time; the Nature version exceeded average human performance on 29 of 49 Atari games.

2. The DQN Family Trifecta (2015–2016, all arXiv links real)

Paper	Year	Problem solved	One-line positioning
van Hasselt et al., Double DQN (arXiv:1509.06461)	2016	Q-value overestimation	Decouples action selection from value estimation — "the online network picks the action, the target network scores it" — easing the systematic overestimation caused by the max operator
Schaul et al., Prioritized Experience Replay (arXiv:1511.05952)	2016	Inefficient replay sampling	Ranks and samples transitions by TD error, spending the sample budget on the most "surprising" transitions
Wang et al., Dueling DQN (arXiv:1511.06581)	2016	State value entangled with action advantage	Splits Q into two streams, V(s) and A(s,a), learning more efficiently "which states are good" through architecture alone

These three, plus the distributional perspective (C51, Bellemare et al. 2017, arXiv:1707.06887) and multi-step returns, were integrated into a single agent by Hessel et al.'s Rainbow (2018, arXiv:1710.02298), which posted the best composite score on Atari at the time. Full background on the Atari case study lives at Atari and Video Games.

3. Silver et al., Mastering the Game of Go with Deep Neural Networks and Tree Search (AlphaGo, 2016, Nature 529)

— One-line positioning: A three-way fusion of supervised learning, reinforcement learning, and MCTS defeated a top human professional — a demonstration of what "search × learning" can do together.

The three-stage training (SL policy network learns from human games → RL policy network sharpens via self-play → value network evaluates positions) is the most frequently asked-about mechanism in interviews. The full story is in Classic Paper Readings and the AlphaGo case study.

4. Silver et al., Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (AlphaZero, 2017, arXiv:1712.01815)

— One-line positioning: Dropping human game records and domain-crafted features, pure self-play + MCTS mastered Go, chess, and shogi with a single algorithm — a declaration of generality.

The difference between AlphaZero and AlphaGo comes down to one word: pure. No SL stage, no hand-crafted features; the policy and value networks are trained from random initialization through self-play alone. It also brought the "be optimistic in the face of uncertainty" principle (a UCB variant) covered on the Multi-Armed Bandits page into MCTS's selection step.

5. Schrittwieser et al., Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model (MuZero, 2020, arXiv:1911.08265)

— One-line positioning: Extends AlphaZero-style planning to settings where the environment is unknown: learning representations, dynamics, and rewards in latent space, then running MCTS on the learned model — planning no longer needs a rules engine.

MuZero is the high-water mark of model-based RL in the "learned planning" direction, and it directly inspired the world-model research that followed (see Frontier Progress).

The RLHF Branch: A New Stream from 2022

This branch asks: a model has knowledge but won't "behave" — how do we make its outputs match human preferences? It swaps the reward from the environment for human feedback, and since 2022 it has been the densest and most engineering-impactful stream of the whole field.

1. Ouyang et al., Training Language Models to Follow Instructions with Human Feedback (InstructGPT, 2022, arXiv:2203.02155)

— One-line positioning: A three-stage pipeline (SFT → reward model → PPO fine-tuning) teaches language models to "follow instructions," with the 1.3B InstructGPT beating the 175B GPT-3 in human evaluations.

The three stages became the standard RLHF recipe. A close reading lives in Classic Paper Readings and the LLM alignment case study.

2. Rafailov et al., Direct Preference Optimization (DPO, 2023, arXiv:2305.18290)

— One-line positioning: A closed-form solution over preference pairs compresses the "reward model + PPO" pipeline into a single direct policy optimization step, slashing training cost and becoming the mainstream of open-source alignment.

DPO's insight: the KL-constrained RLHF objective has an analytical solution, which lets the reward model be embedded implicitly inside the policy — so no explicit reward model and no PPO are needed; training reduces to a classification-style objective over preference pairs. The costs and limitations (no explicit reward control, sensitivity to preference noise) are covered on the RLHF concept page and in Frontier Progress.

3. Bai et al., Constitutional AI: Harmlessness from AI Feedback (RLAIF, 2022, arXiv:2212.08073)

— One-line positioning: Lets AI provide the feedback itself (a "constitution" of principles guides an AI evaluating another AI's outputs), replacing part of the human labeling and scaling harmlessness alignment.

RLAIF is short for "RL from AI feedback." It swaps RLHF's "human preferences" for "AI preferences grounded in explicit principles," breaking through the human-labeling scalability bottleneck — a prelude to online RLHF and RLAIF.

The Multi-Agent Branch: A New Stream from 2017

This branch asks: what happens when many agents learn at the same time, each affecting the others? The single-agent assumption of a "stable environment" breaks down — every agent treats the others as part of its environment, creating non-stationarity that demands new tools.

1. Lowe et al., Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments (MADDPG, 2017, arXiv:1706.02275)

— One-line positioning: Founded the CTDE (centralized training with decentralized execution) paradigm: during training, each critic sees every agent's observations and actions; at execution time, each actor acts on only its own local view.

2. Rashid et al., QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning (2018, arXiv:1803.11485)

— One-line positioning: Factorizes the joint Q-value into a monotonic combination of per-agent Q-values (preserving argmax consistency), performing strongly on StarCraft micromanagement (SMAC).

3. Yu et al., The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games (MAPPO, 2021, arXiv:2103.01955)

— One-line positioning: Pair PPO with a centralized critic that gets shared observations and it beats the specialized MARL algorithms of the day on SMAC, Google Research Football, and Hanabi — "don't underestimate a general-purpose algorithm."

Why multi-agent is hard, the game-theoretic view, and the realities of deployment are all on the Multi-Agent concept page.

Timeline and Cross-References

Compressing the six branches onto a single timeline:

1957 Bellman     ── dynamic programming ──► theoretical foundation
1959 Samuel      ── tabular ──┐
1988 Sutton TD          │      ├──► value-learning main line ──► DQN(2013) ──► Rainbow(2018)
1989/92 Q-learning      │      │
1994 SARSA           ───┘      │
1992 REINFORCE  ── policy gradients ──► TRPO(2015) ──► PPO(2017) ──► RLHF(2022) ──► DPO(2023)
1999 PG theorem         │           └──► SAC(2018)
2013 DQN        ── deep RL ──► AlphaGo(2016) ──► AlphaZero(2017) ──► MuZero(2020)
2017 MADDPG     ── multi-agent ──► QMIX(2018) ──► MAPPO(2021)

How this page relates to the rest of the site:

You want...	Head here
The full chronological narrative	The Evolution of RL (organized by decade; this page is its latitude to that page's longitude)
Mechanism details of tabular + deep RL	Value Learning (the complete thread from DP to DQN)
Mechanism details of policy gradients + PPO	Policy Gradient (from REINFORCE to PPO)
Mechanism details of RLHF	RLHF and Human-Feedback Alignment (three stages, KL, DPO)
Paper-by-paper close readings and interview points	Classic Paper Readings (six landmarks from this map)
Quick terminology lookup	Glossary

How to use this page

Treat it as a cataloging system for the literature. When you pick up any new paper, ask three questions: ① Which branch does it belong to? ② Which key mechanism does it inherit (Bellman, TD, policy gradient, replay, search)? ③ What does it change relative to the most recent paper in the same branch? If you can't answer all three, you haven't actually located the paper yet.

Further Reading

• The Evolution of RL — the longitude to this page's latitude: seven decades of RL by era.
• Classic Paper Readings — close readings of the six most prominent landmarks on this map.
• Value Learning — the mechanics of the dynamic programming and tabular branches, in detail.
• RLHF and Human-Feedback Alignment — the mechanics of the RLHF branch (three stages, KL, DPO).
• Glossary — a quick reference for unfamiliar terms while reading the map.

References

• Bellman, R. (1957). A Markovian Decision Process. Indiana University Mathematics Journal 6(4):679–684. https://doi.org/10.1512/iumj.1957.6.56038
• Samuel, A. L. (1959). Some Studies in Machine Learning Using the Game of Checkers. IBM Journal of Research and Development 3(3):210–229. https://doi.org/10.1147/rd.33.0210
• Sutton, R. S. (1988). Learning to Predict by the Methods of Temporal Differences. Machine Learning 3(1):9–44. http://incompleteideas.net/papers/sutton-88-with-erratum.pdf
• Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning 8(3):279–292. https://link.springer.com/article/10.1007/BF00992698
• Williams, R. J. (1992). Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning. Machine Learning 8(3):229–256. https://link.springer.com/article/10.1007/BF00992696
• Schulman, J., et al. (2015). Trust Region Policy Optimization. arXiv:1502.05477. https://arxiv.org/abs/1502.05477
• Schulman, J., et al. (2017). Proximal Policy Optimization Algorithms. arXiv:1707.06347. https://arxiv.org/abs/1707.06347
• Haarnoja, T., et al. (2018). Soft Actor-Critic. arXiv:1801.01290. https://arxiv.org/abs/1801.01290
• Mnih, V., et al. (2013). Playing Atari with Deep Reinforcement Learning. arXiv:1312.5602. https://arxiv.org/abs/1312.5602
• Hessel, M., et al. (2018). Rainbow: Combining Improvements in Deep Reinforcement Learning. arXiv:1710.02298. https://arxiv.org/abs/1710.02298
• Silver, D., et al. (2016). Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature 529:484–489. https://www.nature.com/articles/nature16961
• Silver, D., et al. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (AlphaZero). arXiv:1712.01815. https://arxiv.org/abs/1712.01815
• Schrittwieser, J., et al. (2020). Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model (MuZero). arXiv:1911.08265. https://arxiv.org/abs/1911.08265
• Ouyang, L., et al. (2022). Training Language Models to Follow Instructions with Human Feedback (InstructGPT). arXiv:2203.02155. https://arxiv.org/abs/2203.02155
• Rafailov, R., et al. (2023). Direct Preference Optimization: Your Language Model is Secretly a Reward Model. arXiv:2305.18290. https://arxiv.org/abs/2305.18290
• Bai, Y., et al. (2022). Constitutional AI: Harmlessness from AI Feedback (RLAIF). arXiv:2212.08073. https://arxiv.org/abs/2212.08073
• Lowe, R., et al. (2017). Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments (MADDPG). arXiv:1706.02275. https://arxiv.org/abs/1706.02275
• Rashid, T., et al. (2018). QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning. arXiv:1803.11485. https://arxiv.org/abs/1803.11485
• Yu, C., et al. (2021). The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games (MAPPO). arXiv:2103.01955. https://arxiv.org/abs/2103.01955