Chapter 6: Tabular Reinforcement Learning
The introduction positions temporal-difference learning as a foundation of reinforcement learning and briefly contrasts tabular and approximation-based methods.
After this chapter you will be able to
- Foundations of reinforcement learning. Explain the roles of generalized policy iteration and temporal-difference learning as foundational ideas in reinforcement learning.
- Temporal Difference Value Update. Explain how TD error and the learning rate update the current state's value without waiting for the final outcome.
- Sampled Bellman Expectation. Distinguish a one-transition TD update from the Bellman equation's expectation over actions and transitions.
- Restaurant scheduling and backward induction. Trace the analytical decisions for one and two hours remaining in the restaurant example.
- Experience and convergence benchmark. Explain how the example uses experience and an analytical benchmark to demonstrate temporal-difference convergence.
- Temporal difference error feedback. Explain how the sign of temporal-difference error guides changes to value estimates.
- Model-free action values. Explain why model-free decision-making learns action values directly and what extra complexity this entails.
- TD bootstrapping and updates. Describe how TD bootstrapping supports incremental learning and why moving to action values requires a choice of next action.
- On-policy and off-policy learning. Distinguish on-policy and off-policy learning using the behavior policy and the policy represented by updates.
- SARSA and Q-learning distinction. Distinguish how SARSA and Q-learning select the next action value used in their temporal-difference error.
- Tabular value representation. Explain what a tabular representation stores and how an agent accesses and updates its values.
- On-policy SARSA update. Explain how SARSA uses its experience tuple and the value of the next action to update the current action value.
- SARSA episode flow. Trace the SARSA process from initialization through action selection, updating, and continuation or episode termination.
- Off-policy learning target. Explain how Q-learning separates the policy that generates experience from the policy it learns.
- Q-learning update workflow. Trace the Q-learning loop and distinguish its update from SARSA’s.
- TD and Monte Carlo continuum. Explain the tradeoff between one-step TD and Monte Carlo learning and how TD(λ) provides a continuum between them.
- Backward credit assignment. Explain how eligibility traces distribute the current TD error backward and enable an online view of TD(λ).
- Trace decay and revisits. Describe how eligibility traces decay and are boosted by visits, including the effect of λ.
- SARSA eligibility traces. Describe how SARSA(λ) applies eligibility traces to on-policy action-value learning.
- Watkins trace resetting. Explain why Watkins's Q(λ) resets traces after a non-greedy action and the resulting tradeoff.
- Compact inventory state. Explain the three features used to represent the gas station state and why the representation must be compact.
- Ordering actions and rewards. Describe the daily ordering choices and how the reward captures the business tradeoff.
- Stochastic daily inventory simulation. Trace how uncertainty and the daily simulation affect inventory over an episode.
- Tabular agent training. Distinguish the Q-learning and SARSA next-state targets and describe how exploration and the training loop use them.
- Eligibility trace agent updates. Explain how eligibility traces spread updates and how SARSA(λ) and Watkins' Q(λ) handle the next action.
- Business performance comparison. Interpret the reported agent results in terms of profitability, stockouts, consistency, and the value of added algorithmic complexity.
What it builds on
- Solving bellman equations: Generalized Policy Iteration (chapter 4) · Generalized policy iteration and its evaluation and improvement components.
- Markov decision process (chapter 2) · Sequential decisions and rewards in a Markov decision process
- The domino decision rule: Bellman equations (chapter 4) · Values expressed in terms of rewards and subsequent values
- Tradeoff between exploitation and exploration (chapter 5) · The exploration–exploitation tradeoff in bandits.
- State: Anatomy of sequential decision making (chapter 2) · state representation for sequential decisions
- Design rewards to be stepwise, whenever possible (chapter 2) · stepwise rewards
- Conceptual framework for designing business environment (chapter 3) · designing an environment for a business problem
Section by section
Introduction
The introduction positions temporal-difference learning as a foundation of reinforcement learning and briefly contrasts tabular and approximation-based methods.
- Foundations of reinforcement learning: Explain the roles of generalized policy iteration and temporal-difference learning as foundational ideas in reinforcement learning.
Why it matters: These two ideas provide a foundation for understanding later reinforcement learning methods. - Value representation approaches: Distinguish tabular methods from function approximation and deep reinforcement learning at the introductory level.
Why it matters: The distinction helps place tabular learning alongside later approaches to estimating values.
Key terms: generalized policy iteration, policy evaluation, policy improvement, temporal-difference learning, tabular methods, function approximation, deep reinforcement learning, V(s), Q(s, a)
6.1 Temporal difference learning
This section introduces temporal-difference learning as an incremental, experience-based way to update value estimates without knowing the full future or environment probabilities.
- Prediction Error Feedback: Explain how a mismatch between prediction and outcome can guide learning, using the neuroscience or supervised-learning analogy.
Why it matters: This feedback pattern provides an intuition for how TD learning improves estimates. - Reinforcement Learning Feedback Challenge: Explain why reinforcement learning cannot simply use a fixed correct label for each decision and why immediate reward alone can be misleading.
Why it matters: This explains why reinforcement learning needs an error signal other than a known correct label. - Temporal Difference Value Update: Explain how TD error and the learning rate update the current state's value without waiting for the final outcome.
Why it matters: The TD update makes it possible to improve value estimates step by step before the final result is known. - Sampled Bellman Expectation: Distinguish a one-transition TD update from the Bellman equation's expectation over actions and transitions.
Why it matters: Sampling lets TD learn from experience without explicitly knowing every transition probability. - Online and Offline Learning: Distinguish online learning from offline learning by when updates occur.
Why it matters: The distinction helps explain how incremental updates can adapt to new information as it arrives.
Key terms: prediction error, learning rate, loss function, immediate reward, labels, sequential decision-making, temporal-difference learning, TD error, discounted value, value of the current state
6.2 A concrete example: restaurant table scheduling
This section uses restaurant table scheduling to compare temporal-difference learning from experience with an analytically calculated optimal solution.
- Restaurant scheduling and backward induction: Trace the analytical decisions for one and two hours remaining in the restaurant example.
Why it matters: The backward calculation gives us a benchmark for judging what the learning algorithm discovers. - Experience and convergence benchmark: Explain how the example uses experience and an analytical benchmark to demonstrate temporal-difference convergence.
Why it matters: The comparison shows how learning from experience can produce useful estimates without a known customer-arrival model. - Temporal difference error feedback: Explain how the sign of temporal-difference error guides changes to value estimates.
Why it matters: This feedback explains how experience corrects the learner's expectations.
Key terms: backward induction, expected value, discount factor, state, temporal-difference learning, convergence, episodes, value estimates, optimal value function, temporal-difference error
6.3 Off policy vs on policy learning
This section explains why model-free TD learning uses action values and distinguishes learning under the behavior policy from learning about a different policy.
- Model-free action values: Explain why model-free decision-making learns action values directly and what extra complexity this entails.
Why it matters: Action values let an agent choose actions without knowing a model of the environment. - Sample-based policy evaluation: Distinguish sample-based model-free learning from dynamic programming's evaluation with known probabilities.
Why it matters: Samples give the agent evidence to learn from when exact transition probabilities are unavailable. - Exploration and sequential decisions: Explain the exploration–exploitation tradeoff and why sequential decisions make it harder than in simple bandits.
Why it matters: Balancing learning and reward matters when current choices affect what the agent can do later. - TD bootstrapping and updates: Describe how TD bootstrapping supports incremental learning and why moving to action values requires a choice of next action.
Why it matters: The choice of future estimate connects incremental TD updates to the policy distinction. - On-policy and off-policy learning: Distinguish on-policy and off-policy learning using the behavior policy and the policy represented by updates.
Why it matters: Separating behavior from the policy being learned allows exploration while updates target a different policy.
Key terms: state values, action values, V(s), Q(s,a), model-free, experience tuples, sampling, state, action, reward
6.4 Tabular Reinforcement Learning: Q-learning and SARSA
This section introduces tabular action-value representation and contrasts the next-action choices used by SARSA and Q-learning.
- SARSA and Q-learning distinction: Distinguish how SARSA and Q-learning select the next action value used in their temporal-difference error.
Why it matters: This difference leads the two methods to learn differently, which matters when decisions carry risk. - Tabular value representation: Explain what a tabular representation stores and how an agent accesses and updates its values.
Why it matters: The table makes the agent's value for each state-action combination directly accessible. - Restaurant Q-value interpretation: Explain what a restaurant scheduling Q-value represents and how the table suggests an action.
Why it matters: Interpreting and comparing Q-values turns the table into a decision aid.
Key terms: SARSA, Q-learning, temporal-difference learning, TD error, action-value function, tabular, lookup table, Q-table, state-action pair, Q-value
6.4.1 SARSA: learning from what you actually do
This section explains SARSA’s on-policy learning process, action selection, and practical tradeoffs.
- On-policy SARSA update: Explain how SARSA uses its experience tuple and the value of the next action to update the current action value.
Why it matters: This is what makes SARSA learn from the policy the agent actually follows. - SARSA episode flow: Trace the SARSA process from initialization through action selection, updating, and continuation or episode termination.
Why it matters: The order of choosing and carrying forward the next action is central to the algorithm. - Epsilon-greedy action selection: Explain how ε-greedy action selection balances exploitation and exploration in SARSA.
Why it matters: The policy needs both to use what it has learned and to explore potentially better actions. - Behavioral realism and tradeoffs: Describe SARSA’s practical strength and limitations when learning from actual behavior.
Why it matters: These tradeoffs help explain when learning from actual behavior is valuable and what it may cost.
Key terms: SARSA, State-Action-Reward-State-Action, on-policy, Q(s,a), Q(s',a'), terminal state, episode, next action, ε-greedy, exploitation
6.4.2 Q-learning: learning from what you should do
This section explains Q-learning’s off-policy update, its basic workflow, and its advantages and risks.
- Off-policy learning target: Explain how Q-learning separates the policy that generates experience from the policy it learns.
Why it matters: This separation lets the agent learn from actions that are not always its current best choice. - Q-learning update workflow: Trace the Q-learning loop and distinguish its update from SARSA’s.
Why it matters: The next-state maximum is the key operational difference between Q-learning and SARSA. - Benefits and optimism risks: Describe Q-learning’s stated advantages and the risks of its optimistic target.
Why it matters: These tradeoffs help explain when Q-learning’s efficiency may come with an overly optimistic assessment.
Key terms: Q-learning, off-policy learning, behavior policy, greedy policy, Q(s,a), ε-greedy, optimistic bootstrapping, maximum Q-value, batch learning, overoptimism
6.5 TD(λ) and Eligibility traces
This section explains how TD(λ) uses eligibility traces to distribute credit over earlier decisions and extends the approach to SARSA and Q-learning.
- TD and Monte Carlo continuum: Explain the tradeoff between one-step TD and Monte Carlo learning and how TD(λ) provides a continuum between them.
Why it matters: This tradeoff explains why we might want to learn from more than one step without always waiting for an entire episode. - Backward credit assignment: Explain how eligibility traces distribute the current TD error backward and enable an online view of TD(λ).
Why it matters: Traces let a later outcome influence earlier decisions without waiting to calculate future returns. - Trace decay and revisits: Describe how eligibility traces decay and are boosted by visits, including the effect of λ.
Why it matters: The decay and visit rules determine how far back and how strongly credit can travel. - Accumulating and replacing traces: Distinguish accumulating from replacing traces when a state is revisited.
Why it matters: The choice changes how much repeated visits contribute to credit. - SARSA eligibility traces: Describe how SARSA(λ) applies eligibility traces to on-policy action-value learning.
Why it matters: SARSA(λ) brings backward credit assignment into action selection while learning from the agent's actual behavior. - Watkins trace resetting: Explain why Watkins's Q(λ) resets traces after a non-greedy action and the resulting tradeoff.
Why it matters: The reset shows how off-policy learning changes the way traces can carry credit through exploratory behavior.
Key terms: TD(0), Monte Carlo, TD(λ), n-step returns, bias–variance tradeoff, eligibility trace, credit assignment, TD error, forward view, backward view
6.6 Gas station fuel purchase scheduling with tabular methods
This section models gas station fuel purchasing as an episodic inventory problem, implements tabular agents, and compares their business performance.
- Compact inventory state: Explain the three features used to represent the gas station state and why the representation must be compact.
Why it matters: A usable state must capture the inventory situation without making the table too large to learn. - Ordering actions and rewards: Describe the daily ordering choices and how the reward captures the business tradeoff.
Why it matters: The action and reward design connects the agent's decisions to the station's financial priorities. - Stochastic daily inventory simulation: Trace how uncertainty and the daily simulation affect inventory over an episode.
Why it matters: The simulation exposes the agent to uncertain demand and delayed consequences of ordering. - Tabular agent training: Distinguish the Q-learning and SARSA next-state targets and describe how exploration and the training loop use them.
Why it matters: The target choice and exploration schedule determine what each agent learns from its experience. - Eligibility trace agent updates: Explain how eligibility traces spread updates and how SARSA(λ) and Watkins' Q(λ) handle the next action.
Why it matters: Traces help assign credit to earlier decisions, but off-policy learning needs special handling of exploratory actions. - Business performance comparison: Interpret the reported agent results in terms of profitability, stockouts, consistency, and the value of added algorithmic complexity.
Why it matters: A deployment choice should reflect profit, customer service, and risk tolerance rather than a single score or algorithm name.
Key terms: current_inventory, pending_sum, next_arrival_time, Markovian, state space, action space, reward function, stockout penalties, holding costs, ordering costs
6.7 Summary
Where this is used later
- From tabular to linear function approximation (chapter 8) · Develops the transition from tabular representations to function approximation.
- (chapter intro) (chapter 8) · Tabular reinforcement learning represents values in tables.
- DQN theory: Q-learning meets neural networks (chapter 8) · Deep Q-networks build on Q-learning.
- Designing the evaluation (chapter 12) · evaluation must reflect the objectives and risks relevant to deployment
Concepts explained in this chapter
- SARSA(λ)SARSA(λ) is an on-policy temporal-difference algorithm that combines SARSA updates with eligibility traces.
- eligibility traceAn eligibility trace is a decaying record of recently visited state-action pairs that determines how temporal-difference errors are assigned backward through them.
- TD(λ)TD(lambda) is a family of temporal-difference methods that combines bootstrapped value updates with eligibility traces to assign credit across multiple steps.
- TD-learningTemporal-difference learning updates value estimates incrementally using observed rewards and estimates of subsequent values.
- tabular methodTabular reinforcement learning stores value estimates or policy information explicitly in lookup tables indexed by states or state-action pairs.
- online learningOnline learning updates a model incrementally as data or interaction outcomes become available rather than waiting for a complete dataset or episode.
- temporal-difference errorA temporal-difference error is the difference between a target formed from an immediate reward and a discounted estimate of future value and the current value estimate.
- Q(lambda)Q(lambda) is an off-policy action-value learning algorithm that combines Q-learning targets with eligibility traces and resets traces after non-greedy actions.
- inventory managementInventory management is the planning and control of replenishment and stock levels to balance availability and inventory-related costs.
- stockoutA stockout is a condition in which available inventory is insufficient to satisfy current demand.
- on-policy methodOn-policy learning is reinforcement learning in which the policy generating experience is the same policy being evaluated or improved.
- off-policy methodOff-policy learning is reinforcement learning in which a target policy is evaluated or improved using experience generated by a potentially different behavior policy.
- Watkins's Q(λ)Watkins's Q(λ) is an off-policy Q-learning variant that resets eligibility traces when a non-greedy action is taken.
- action-value functionAn action-value function maps a state-action pair to the expected return from taking the action and then following a policy.
- Q-learningQ-learning is a model-free reinforcement-learning algorithm that estimates the optimal action-value function through temporal-difference updates using the maximum estimated value of the next state.
- behavior policyA behavior policy is the policy that selects actions and generates experience for a learning algorithm.
- accumulating traceAn accumulating trace increases by a fixed increment when its associated state or state-action pair is visited, in addition to retaining its decayed value.
- bias-variance tradeoffThe bias-variance tradeoff is the balance between systematic estimation error and variability across samples or outcomes.
- n-step TDn-step TD is a temporal-difference method whose target uses rewards and state estimates across n future steps.
- replacing traceA replacing trace sets the trace of a visited state or state-action pair to a fixed maximum value instead of accumulating repeated increments.
- learning rateA learning rate is a numerical step-size parameter that controls how strongly an update changes an estimate or model parameter.
- model-free methodModel-free learning is reinforcement learning in which an agent learns action selection directly from experience without an explicit environment transition model.
- target policyA target policy is the decision rule whose value or action preferences an off-policy learning algorithm estimates or optimizes.
- convergenceConvergence is the approach of successive numerical estimates or policies toward a stable limiting result.
- restaurant scheduling problemA finite-horizon decision problem in which a restaurant chooses when to seat parties to maximize expected revenue under uncertain arrivals.
- value functionA value function estimates the expected cumulative return from a state or state-action pair under a specified policy or optimal behavior.
- bootstrappingBootstrapping is an estimation technique that updates a prediction using another prediction or value estimate rather than waiting for a complete realized outcome.
- credit assignmentCredit assignment is the problem of determining which earlier decisions contributed to a later success or failure.
- feature engineeringFeature engineering is the construction or transformation of input features into representations suitable for a model or learning algorithm.
- supplier lead timeSupplier lead time is the elapsed time between placing an order with a supplier and receiving it.
- objective functionA mathematical quantity that a learning or optimization procedure seeks to minimize or maximize.
- Monte Carlo simulationMonte Carlo estimation approximates a quantity by averaging values obtained from random samples.
- dynamic programmingDynamic programming is an algorithmic technique that solves sequential decision or optimization problems by decomposing them into overlapping subproblems and combining their solutions.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
