Artificial intelligence and reinforcement learning

Artificial intelligence is broader than fitting a predictor. An intelligent agent may need to search, reason with incomplete information, choose actions whose effects unfold over time, learn from interaction, and account for other agents. This chapter connects classical AI abstractions to modern reinforcement learning (RL) without treating a high reward in a simulator as evidence of safe real-world behaviour.

Latest literature discovery audit: 2 October 2026. Existing paper reviews retain their individual source-check dates.

Individual ICLR oral-paper studies retain their 19 September 2026 source-check dates; the later discovery audit does not re-date that evidence.

Prerequisites

Complete probability, expectation, conditional independence, optimization, and uncertainty in mathematics, probability, and statistics. You should understand supervised empirical risk but do not need deep learning until the deep-RL section. Basic algorithms, recursion, graphs, and Python are helpful.

Learning objectives

After this chapter, you should be able to:

• formalize a problem by its state, actions, transition model, goal, and cost;
• choose and analyze uninformed, heuristic, adversarial, or constraint search;
• represent facts and uncertainty with logic or probabilistic graphical models;
• write Bellman expectation and optimality equations for a Markov decision process;
• distinguish planning, Monte Carlo estimation, temporal-difference learning, value-based control, and policy gradients;
• explain on-policy, off-policy, online, model-based, and offline RL;
• identify partial observability, support mismatch, reward misspecification, and unsafe exploration;
• evaluate a sequential policy with learning curves, uncertainty, and auditable logged data rather than one best return.

Agent and problem formulation

An agent receives observations, maintains information, and chooses actions. Separate:

Object	Meaning	Common mistake
environment state	information sufficient for the modelled future	calling a partial sensor measurement “the state”
observation	information delivered to the agent	assuming it contains all relevant history
action	a choice available at that point	including actions that cannot be executed
transition	how state changes after an action	ignoring stochasticity or other agents
goal / cost / reward	the encoded preference	assuming the proxy exactly represents human value
policy	a mapping from information to action distribution	confusing the learned policy with its training algorithm

A good formulation is often more important than a sophisticated solver. In a clinical setting, for example, a retrospective prediction score is not yet a treatment policy: actions change outcomes, logged care has confounding, and exploration can harm people.

Search and planning

State-space search

A deterministic search problem specifies an initial state, actions, successor function, goal test, and path cost.

• breadth-first search is complete for finite branching and unit costs but stores a wide frontier;
• depth-first search uses less memory but can follow an infinite or poor branch;
• uniform-cost search expands the lowest accumulated path cost;
• A* expands according to f(n) = g(n) + h(n), combining path cost with a heuristic estimate.

An admissible heuristic never overestimates remaining cost. Consistency imposes a triangle-like condition and supports efficient graph search. Heuristic quality changes work, not the definition of an optimal solution. Record node expansion, memory, and solution cost rather than runtime alone.

Constraint satisfaction

A constraint-satisfaction problem defines variables, domains, and constraints. Backtracking can be improved with variable/value ordering, forward checking, arc consistency, and constraint propagation. Factor-graph structure explains which variables interact. Scheduling and assignment problems often fit this formulation better than a neural predictor.

Mackworth’s consistency framework distinguishes local consistency conditions from global satisfiability. Propagation can prune domains substantially, but it does not replace search unless the constraint structure provides the required guarantee.

Adversarial and multi-agent search

Minimax optimizes against an opponent in a zero-sum, perfect-information game. Alpha–beta pruning removes branches that cannot change the result without changing the exact minimax value. Evaluation functions and depth limits introduce approximation.

Chance nodes model known stochastic outcomes; general-sum, partially observed, and many-player settings need richer game-theoretic models. Self-play changes the data distribution throughout training, so checkpoint selection and opponent pools affect the result.

UCT combines Monte Carlo tree search with an upper-confidence action rule, balancing expansion of uncertain branches against exploitation of high-value branches. Its result depends on rollout policy, simulation budget, value estimates, tree reuse, and the environment’s branching structure.

Logic and probabilistic reasoning

Logic

Propositional logic represents truth-functional statements. First-order logic adds objects, predicates, variables, and quantifiers. Entailment asks whether every model of a knowledge base satisfies a query; proof procedures manipulate syntax to establish that relation.

Logic makes assumptions inspectable but requires a vocabulary and knowledge base. Open-world versus closed-world assumptions, inconsistent facts, uncertain evidence, and grounding cost must be explicit. A language model producing plausible text is not by itself a sound theorem prover.

Graphical models

A Bayesian network factorizes a joint distribution according to a directed acyclic graph. A Markov random field uses undirected factors. Conditional-independence structure can reduce inference and clarify assumptions.

Pearl’s belief-network formulation connects graph structure to local message propagation. Exact propagation guarantees depend on topology; loopy graphs, approximate factors, and learned conditional distributions require separate accuracy and calibration checks.

Exact variable elimination trades computation for intermediate factor size. Belief propagation is exact on trees and approximate on loopy graphs. Sampling and variational inference approximate otherwise intractable quantities. Causal direction cannot generally be recovered from observational conditional independence alone.

Decisions under uncertainty

Decision theory selects an action by expected utility:

a* = arg max_a E[U(outcome) | information, action a].

The posterior model, utility, time horizon, and risk attitude all matter. Maximum predictive accuracy need not maximize utility. Value of information asks whether an additional measurement changes the optimal expected utility enough to justify its cost.

Markov decision processes

An infinite- or finite-horizon Markov decision process (MDP) is defined by (S, A, P, R, γ):

• S: states;
• A: actions;
• P(s'|s,a): transition distribution;
• R: reward distribution or expected immediate reward;
• γ: discount factor for continuing tasks.

A policy π(a|s) induces a return G_t = Σ_k γ^k R_(t+k+1). Its state value is V^π(s) = Eπ[G_t | S_t=s]; its action value conditions additionally on the first action.

The Bellman expectation equation is a consistency relation:

V^π(s) = Σ_a π(a|s) Σ_s' P(s'|s,a)
         [R(s,a,s') + γ V^π(s')].

The optimality equation replaces the policy average with the best action. Discounting can ensure a finite objective and express time preference, but the chosen γ also changes which behaviour is optimal.

Dynamic programming

When the transition and reward model are known and the state space is manageable:

• policy evaluation computes V^π;
• policy improvement acts greedily with respect to that value;
• policy iteration alternates the two;
• value iteration repeatedly applies the Bellman optimality backup.

Stopping tolerance determines approximation error. A tabular dynamic-programming solution is a reference for testing an RL implementation.

Learning from experience

Monte Carlo and temporal-difference learning

Monte Carlo methods learn from complete sampled returns and do not bootstrap, but can have high variance and require episode completion. Temporal-difference (TD) learning updates from a reward plus a current value estimate:

δ_t = R_(t+1) + γ V(S_(t+1)) - V(S_t).

Bootstrapping reduces some variance but introduces bias and coupling to the current estimate. Multi-step returns and eligibility traces interpolate between endpoints.

Control and behaviour policy

SARSA learns an action value using the action actually selected by the current behaviour policy; Q-learning uses a greedy target and is off-policy. Off-policy learning separates the policy generating data from the target policy, creating importance-weight and distribution-shift problems.

Exploration mechanisms include epsilon-greedy actions, optimism, upper-confidence bounds, posterior sampling, intrinsic objectives, and entropy bonuses. Exploration is not free: in physical, financial, or clinical environments, trying uncertain actions may be unacceptable.

Function approximation and the deadly triad

Large state spaces require features or learned representations. Combining function approximation, bootstrapping, and off-policy training can diverge—the “deadly triad.” Replay buffers, target networks, clipped objectives, normalization, and conservative updates are engineering responses, not universal convergence guarantees.

Deep reinforcement learning

Value-based methods

Deep Q-Networks (DQN) approximate action values with a neural network and stabilize learning using experience replay and a target network. Extensions address overestimation, prioritized replay, noisy exploration, distributional returns, and multi-step targets. Benchmark improvements can depend on a bundle of interventions; use ablations and a shared evaluation protocol.

Policy gradients and actor–critic

The policy-gradient theorem gives a gradient proportional to

E[∇θ log πθ(a|s) Q^π(s,a)].

A baseline can reduce variance without changing the expectation. Actor–critic methods learn both a policy and a value-based critic. Generalized advantage estimation trades bias and variance across temporal scales.

Asynchronous Advantage Actor–Critic uses parallel actor-learners to decorrelate experience without replay. Soft Actor-Critic instead combines off-policy updates with a maximum-entropy objective for continuous control. Compare their data reuse, exploration, target-network, entropy-temperature, synchronization, and wall-clock assumptions rather than treating “actor–critic” as one algorithm.

Trust-region methods constrain policy change. Proximal Policy Optimization (PPO) uses a clipped surrogate as a practical approximation, but clipping does not guarantee a hard trust region. Report rollout horizon, advantage normalization, entropy, observation/reward scaling, update epochs, and environment steps.

Model-based learning and search

Dyna interleaves real experience, learned-model updates, and simulated planning. AlphaGo Zero combines self-play, a policy/value network, and Monte Carlo tree search in a known game simulator. MuZero learns latent dynamics sufficient for planning without reconstructing observations. Dreamer-style agents learn latent world models and optimize behaviour through imagined trajectories.

Learned models can exploit their own errors. Evaluate multi-step calibration, planning horizon, uncertainty, and real-environment interactions—not only imagined return.

Offline RL and sequential data

Offline RL learns from a fixed logged dataset without new exploration. The central problem is support: a learned policy may choose actions rarely or never observed, where value estimates are extrapolations. Conservative Q-Learning penalizes unsupported action values. Sequence-modelling approaches such as Decision Transformer condition autoregressive action prediction on desired return and history.

Implicit Q-Learning avoids evaluating unseen actions during value fitting, then uses advantage-weighted behavioural cloning to extract a policy. This reduces one source of extrapolation but does not create coverage where the logged behaviour has none.

Neither eliminates causal and coverage requirements. Record:

• who or what generated the behaviour data;
• observation and action coverage;
• missing variables that affected actions and outcomes;
• episode termination and censoring;
• reward construction and delayed outcomes;
• overlap between target and behaviour policies.

Off-policy evaluation can use importance sampling, model-based estimators, direct value estimation, or doubly robust combinations. Diagnostics such as effective sample size and weight tails are essential. A high estimated value under weak overlap is not reliable deployment evidence.

Partial observability, safety, and alignment

In a partially observable MDP, an observation is insufficient to identify the state. A belief state is a posterior over states given action-observation history. Recurrent memory is an approximation unless it is shown to retain decision-relevant history.

Safety requires more than adding a negative reward:

• constraints may need to hold during learning, not only in expectation;
• rare catastrophic outcomes are poorly estimated by average return;
• reward hacking exploits gaps between proxy and intent;
• distribution shift changes dynamics and observation meaning;
• human feedback contains disagreement, bias, and strategic effects;
• an apparently interpretable policy can still depend on spurious variables.

Define a fallback, monitoring rule, intervention authority, and deployment boundary. For high-stakes domains, retrospective offline results normally motivate prospective validation—not autonomous action.

Staged resources and primary readings

Search, reasoning, and probabilistic AI

Order	Stage	Resource or primary work · year · status	Read it for
1	broad map	Artificial Intelligence: A Modern Approach — official author site; fourth edition 2020	agents, search, games, logic, uncertainty, decisions, and learning
2	executable course	Stanford CS221: Artificial Intelligence — official course site	problem formulation, search, MDPs, games, graphical models, and logic
3	optimal search	A Formal Basis for the Heuristic Determination of Minimum Cost Paths — 1968 · IEEE Transactions on Systems Science and Cybernetics	A*, admissible heuristics, and optimality conditions
4	constraint propagation	Consistency in Networks of Relations — 1977 · Artificial Intelligence	node, arc, and path consistency as pruning conditions rather than global solutions
5	probabilistic reasoning	Fusion, Propagation, and Structuring in Belief Networks — 1986 · Artificial Intelligence	graphical factorization and local belief propagation
6	simulation-based planning	Bandit Based Monte-Carlo Planning — 2006 · ECML	UCT exploration, tree growth, and finite simulation budgets
7	probabilistic reasoning	Probabilistic Machine Learning: An Introduction — 2022 · MIT Press	graphical models, inference, decision theory, and a shared notation

Reinforcement-learning progression

Order	Stage	Primary paper or resource · year · venue/status	Read it for
1	foundation	Reinforcement Learning: An Introduction — 2018 · second edition, MIT Press; publisher page	MDPs, dynamic programming, Monte Carlo, TD, control, approximation, and planning
2	integrated planning	Integrated Architectures for Learning, Planning, and Reacting Based on Approximating Dynamic Programming — 1990 · ICML proceedings	the Dyna connection between model learning and planning
3	off-policy control	Q-learning — 1992 · Machine Learning	model-free off-policy control and convergence setting
4	policy gradient	Policy Gradient Methods for Reinforcement Learning with Function Approximation — 1999 · NeurIPS	the policy-gradient theorem and compatible approximation
5	deep value learning	Human-level control through deep reinforcement learning — 2015 · Nature	replay, target networks, and DQN evaluation
6	constrained policy update	Trust Region Policy Optimization — 2015 · ICML	monotonic-improvement motivation and trust-region optimization
7	asynchronous actor–critic	Asynchronous Methods for Deep Reinforcement Learning — 2016 · ICML	parallel actor-learners, on-policy updates, and decorrelated experience
8	practical policy update	Proximal Policy Optimization Algorithms — 2017 · arXiv technical report	the clipped surrogate and implementation simplicity
9	planning with self-play	Mastering the game of Go without human knowledge — 2017 · Nature	AlphaGo Zero’s search, policy/value learning, and self-play
10	maximum-entropy control	Soft Actor-Critic — 2018 · ICML	off-policy stochastic actor–critic learning and entropy-temperature trade-offs
11	latent model planning	Mastering Atari, Go, chess and shogi by planning with a learned model — 2020 · Nature	MuZero’s latent dynamics and tree search
12	conservative offline RL	Conservative Q-Learning for Offline Reinforcement Learning — 2020 · NeurIPS	pessimistic value learning under logged-data support limits
13	implicit offline RL	Offline Reinforcement Learning with Implicit Q-Learning — 2022 · ICLR	expectile value fitting and policy extraction without querying unseen actions
14	sequence-modelled control	Decision Transformer: Reinforcement Learning via Sequence Modeling — 2021 · NeurIPS	return-conditioned autoregressive policies and offline evaluation
15	current world models	Mastering diverse control tasks through world models — 2025 · Nature	DreamerV3’s learned latent dynamics, imagined behaviour learning, and cross-domain evidence

For current implementations and lecture material, use the official Berkeley CS285 Deep Reinforcement Learning site. Treat lecture code as a learning reference; reproduce paper claims from versioned implementations and environments.

Controlled labs

Lab A: search

Implement breadth-first search, uniform-cost search, and A* on the same weighted grid. Use zero, Manhattan, and one deliberately inadmissible heuristic. Report path cost, expanded nodes, peak frontier size, and whether optimality is preserved.

Lab B: known MDP

Construct a small stochastic gridworld whose transition matrix and optimal solution are known.

1. Run policy evaluation, policy iteration, and value iteration to a documented tolerance.
2. Learn with Monte Carlo, SARSA, and Q-learning using the same environment steps.
3. Plot mean return and interval across independently seeded runs.
4. Compare learned values with the dynamic-programming reference.
5. Change γ, stochasticity, and exploration one at a time; explain the policy change.

Lab C: offline support failure

Generate logged trajectories from a behaviour policy that rarely visits one region. Train a value method and a conservative offline method. Evaluate with simulator ground truth, then pretend only logs are available and compare an off-policy estimate. Measure action coverage, importance-weight tails, effective sample size, and error in the poorly supported region.

Freeze environment version, wrappers, seeds, episode limit, reward transformation, training interactions, evaluation episodes, and hyperparameter trials.

Common failure modes

• Calling an observation a Markov state without testing missing history.
• Designing reward after inspecting test behaviour.
• Comparing agents with different environment interactions or tuning budgets.
• Reporting the best episode or seed instead of a learning-curve distribution.
• Evaluating on the same stochastic seeds or opponent set used for selection.
• Treating simulator success as evidence that real transition dynamics are correct.
• Ignoring termination, truncation, reward scale, and wrapper implementation.
• Using an offline policy outside logged action support.
• Reporting an off-policy estimate without overlap and weight diagnostics.
• Assuming PPO clipping guarantees a trust region or stable improvement.
• Treating a language model’s chain of thought as verified logical reasoning.
• Deploying exploratory behaviour where actions can cause irreversible harm.

Self-check

Without notes, answer:

1. When are uniform-cost search and breadth-first search equivalent?
2. What do admissibility and consistency guarantee for A*?
3. How does conditional independence reduce graphical-model inference?
4. What is the difference between a predictive score and expected utility?
5. Derive the Bellman expectation equation from one transition.
6. How do Monte Carlo and TD targets differ?
7. Why can off-policy bootstrapping with function approximation diverge?
8. What do replay and target networks change in DQN?
9. Why is PPO’s clipped objective not a deployment safety guarantee?
10. What does support mismatch invalidate in offline RL?

Exit task

Formalize one sequential decision problem twice: first as search or a known MDP, then as a learned-policy problem. Specify observation, latent state, actions, transitions, reward/utility, horizon, behaviour policy, constraints, and fallback. Implement a small reference solution and compare it with a learned method under fixed interaction and tuning budgets. Report uncertainty, support, a reward failure, and the evidence still needed before real-world use.

Predictive representations for reward-selected control

TD-JEPA connects non-contrastive latent prediction to temporal-difference learning. Read the state/action input contract and downstream task-vector inference before interpreting zero-shot control.

Primary paper · year · evidence	Core idea and why to read it	Official resources
TD-JEPA: Latent-predictive Representations for Zero-Shot Reinforcement LearningMarco Bagatella, Matteo Pirotta, Ahmed Touati, Alessandro Lazaric, Andrea Tirinzoni2026 · ICLR · peer-reviewedOfficial ICLR 2026 oral and full proceedings manuscript checked. Reward-free state–action transitions, not action-free video. Zero-shot policy selection still requires reward observations for task-vector inference. Theoretical assumptions, benchmark-specific actor inputs and mixed OGBench comparisons are qualified in the source-checked review; no WSI evaluation.	TD-JEPA learns state and task representations from reward-free transitions so that a new reward can select a policy without task-specific policy fine-tuning. Its distinguishing move is temporal-difference bootstrapping in a joint-embedding predictive architecture: predicting accumulated future task features connects representation learning to zero-shot control.	Official proceedings record · OpenReview · Official implementation

Reading question: What future quantity is predicted, what prevents collapse, and what reward information is still needed at deployment?

Evidence boundary: Restricted theory and simulator-specific actor inputs do not prove arbitrary video or pathology-control validity.

Complete maintained paper route

20 canonical readings · 1968–2026· route reviewed through October 2, 2026.

This is the complete structured list for this chapter, ordered chronologically from earlier foundations toward current work. The explanatory ladder above highlights the shortest conceptual route; this list also includes important branches, benchmarks, and current endpoints. It is generated from the same deduplicated catalog used by the AI background registry and My Library, so a future catalog update appears here automatically.

Show all 20 readings in maintained order

1. #11968IEEE Transactions on Systems Science and CyberneticsPeer reviewedL1–L2

   A Formal Basis for the Heuristic Determination of Minimum Cost Paths

   Peter E. Hart, Nils J. Nilsson, and Bertram Raphael

   Metadata checked 2026-07-27

2. #21977Artificial IntelligencePeer reviewedL2

   Consistency in Networks of Relations

   Alan K. Mackworth

   Metadata checked 2026-07-28

3. #31986Artificial IntelligencePeer reviewedL2

   Fusion, Propagation, and Structuring in Belief Networks

   Judea Pearl

   Metadata checked 2026-07-28

4. #41990ICMLPeer reviewedL2

   Integrated Architectures for Learning, Planning, and Reacting Based on Approximating Dynamic Programming

   Richard S. Sutton

   Metadata checked 2026-07-27

5. #51992Machine LearningPeer reviewedL2

   Q-learning

   Christopher J. C. H. Watkins and Peter Dayan

   Metadata checked 2026-07-27

6. #61999NeurIPSPeer reviewedL2–L3

   Policy Gradient Methods for Reinforcement Learning with Function Approximation

   Richard S. Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour

   Metadata checked 2026-07-27

7. #72006ECMLPeer reviewedL2

   Bandit Based Monte-Carlo Planning

   Levente Kocsis and Csaba Szepesvári

   Metadata checked 2026-07-28

8. #82015NaturePeer reviewedL2

   Human-level Control through Deep Reinforcement Learning

   Volodymyr Mnih et al.

   Metadata checked 2026-07-27

9. #92015ICMLPeer reviewedL2

   Trust Region Policy Optimization

   John Schulman et al.

   Metadata checked 2026-07-27

10. #102016ICMLPeer reviewedL2

    Asynchronous Methods for Deep Reinforcement Learning

    Volodymyr Mnih et al.

    Metadata checked 2026-07-28

11. #112017arXivTechnical reportL2

    Proximal Policy Optimization Algorithms

    John Schulman et al.

    Metadata checked 2026-07-27

12. #122017NaturePeer reviewedL2–L3

    Mastering the Game of Go without Human Knowledge

    David Silver et al.

    Metadata checked 2026-07-27

13. #132018ICMLPeer reviewedL2

    Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor

    Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine

    Metadata checked 2026-07-28

14. #142020NaturePeer reviewedL2–L3

    Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model

    Julian Schrittwieser et al.

    Metadata checked 2026-07-27

15. #152020NeurIPSPeer reviewedL3

    Conservative Q-Learning for Offline Reinforcement Learning

    Aviral Kumar et al.

    Metadata checked 2026-07-27

16. #162021NeurIPSPeer reviewedL3

    Decision Transformer: Reinforcement Learning via Sequence Modeling

    Lili Chen et al.

    Metadata checked 2026-07-27

17. #172022ICLRPeer reviewedL2–L3

    Offline Reinforcement Learning with Implicit Q-Learning

    Ilya Kostrikov, Ashvin Nair, and Sergey Levine

    Metadata checked 2026-07-28

18. #182025NaturePeer reviewedL3

    Mastering Diverse Control Tasks through World Models

    Danijar Hafner et al.

    Metadata checked 2026-07-27

19. #192026arXivPreprintL3

    On-policy Distillation with Verifiable Reward

    Wenze Lin, Jiale Zhao, Xitai Jiang, Songde Rao, Yining Li, Shenzhi Wang, Bingxiang He, and Gao Huang

    arXiv v1 preprint submitted 25 August 2026; evaluation is limited to the reported verifiable reasoning tasks.

    Official artifacts: Official implementation

    Metadata checked 2026-08-30

20. #202026ICLRPeer reviewedL3

    TD-JEPA: Latent-predictive Representations for Zero-Shot Reinforcement Learning

    Marco Bagatella, Matteo Pirotta, Ahmed Touati, Alessandro Lazaric, Andrea Tirinzoni

    Official ICLR 2026 oral and full proceedings manuscript checked. Reward-free state–action transitions, not action-free video. Zero-shot policy selection still requires reward observations for task-vector inference. Theoretical assumptions, benchmark-specific actor inputs and mixed OGBench comparisons are qualified in the source-checked review; no WSI evaluation.

    Official artifacts: Official proceedings record · OpenReview · Official implementation

    Metadata checked 2026-09-19