Reinforcement Learning: An Introduction

Both primary title blocks give Reinforcement Learning: An Introduction and Richard S. Sutton and Andrew G. Barto. The landing page explicitly gives First Edition, MIT Press, Cambridge, MA, 1998 and distinguishes a linked second edition. The ebook contents place Planning and Learning in Chapter 9.

The supplied archive contains HTML and retrieval provenance, with no PDF or linked scientific image files. The HTML references external images for the interaction diagram, Dyna architecture, algorithm, and results; the selected extraction marks these images omitted. Their captions and surrounding prose survive, but the original graphics cannot be inspected from this artifact.

The problem is learning actions that maximize reward through trial and error with delayed consequences; the section explains the exploration/exploitation tradeoff.

Defines policy, reward function, value function, and optional environment model; a model can predict next state and reward and support planning before actual experience.

The agent receives a state representation, selects an action, and subsequently receives reward and a new state. Its boundary describes control rather than physical embodiment or knowledge.

The prose defines return from future rewards, distinguishes episodic and continuing interaction, and motivates discounting. Displayed definitions and many symbols are omitted images.

State preprocessing is assumed given; constructing or learning it is outside the treatment. A Markov state retains relevant past information, and the book's theory assumes Markov signals even though practical representations may violate this.

State values predict expected return under a policy; action values condition on a first action and then that policy. The Bellman discussion relates values to rewards and successor values; equation images themselves are unavailable.

The prose contrasts one-step lookahead using state values with selecting a maximizing action directly from action values, which cache the one-step search results.

Exact solution requires adequate model knowledge, computation, and Markov structure. Memory and per-step computation constrain policies, value functions, and models even with known dynamics.

DP assumes a complete MDP model. Evaluation uses expected rewards and successor values; improvement constructs a greedy policy. Policy iteration alternates these computations; value iteration truncates evaluation to one sweep while incorporating improvement.

GPI allows evaluation and improvement to interact at different granularities. The summary explicitly distinguishes cases with convergence proofs from cases where GPI provides an organizing interpretation without a proof.

Models predict responses to state-action inputs. Distribution models describe outcomes and probabilities; sample models generate individual outcomes. Planning uses models to produce or improve a policy through backups on simulated experience.

Dyna-Q combines online acting, direct one-step tabular Q-learning, model learning, and planning. Its deterministic model stores the most recently observed next state and reward. Planning queries previously experienced pairs and applies the same learning method to simulated transitions.

The maze has 47 states and four deterministic movement actions. Results average 30 repetitions with matched initial seeds. Prose reports about 25 episodes to near-optimal performance without planning and faster learning with more planning. Planning budgets and several hyperparameters are omitted images. Section 9.9 attributes the Dyna architecture to Sutton (1990) and bases these results on that work. The Figure 9.5 caption says S to S, while the task prose explicitly defines goal G and reset to S; this report follows the task prose.

Model errors can arise from stochastic sampling, imperfect generalization, or environmental change. The blocking example exposes an obsolete path; the shortcut example can leave a better path undiscovered. Dyna-Q+ rewards simulated transitions involving actions untried for longer in the real environment; the formula is omitted.

A priority queue orders consequential backups by anticipated value change and propagates effects to predecessor pairs. The section notes that function approximation complicates identifying and processing the many affected states.

Full backups consider all possible successors, avoiding sampling error but costing more; sample backups use one successor. The prose emphasizes comparing computational requirements and suggests sample backups for large problems with substantial stochastic branching. The displayed equations and analysis curve are unavailable.

Both allocations use one-step full tabular backups. Uniform updates cycle through pairs; on-policy updates follow simulated episodes. The upper study averages 200 random tasks with 1,000 states, two actions, branching factors 1, 3, and 10, and termination probability 0.1 per transition. Greedy start-state value is evaluated against backup count. Prose reports an early on-policy advantage and a long-run disadvantage, with conclusions limited by the task generator. The plot and exploration setting are unavailable.

Heuristic search evaluates continuation-tree leaves, backs up values to the current action choices, selects an action, and conventionally discards backed-up values. It focuses computation on the current state and possible successors.

Learning and planning can update the same estimated value function from different sources of experience. The summary contrasts predecessor-focused prioritized sweeping, successor-focused heuristic search, and on-policy trajectory sampling.