Source-linked AI summary
When Waiting is not an Option : Learning Options with a Deliberation Cost
Jean Harb, Pierre-Luc Bacon, Martin Klissarov, Doina Precup
TL;DR
The paper addresses the unresolved question of what makes learned options good when agents have bounded computational resources. It formulates deliberation cost within bounded rationality and derives gradient-based learning methods. In ALE experiments, the approach improves performance and yields more interpretable, persistent options.
Problem
Existing work increasingly explains how to learn options, but lacks a precise account of what good options should be under agents’ resource limitations.
Method
The paper defines good options through bounded rationality and deliberation cost, implementing the objective with gradient-based option-critic learning.
Results
The approach yields good performance and options that are intuitive and do not shrink over time.
Takeaways & Limitations
Deliberation cost incentivizes options to persist longer by making frequent switching costly and can encode additional agent limitations.
Takeaways & Limitations
With λ = 0, termination learning evaluates only immediate computational cost and may miss lower overall cost achievable through less favorable immediate costs.
Abstract
from arXiv · showhide
Recent work has shown that temporally extended actions (options) can be learned fully end-to-end as opposed to being specified in advance. While the problem of "how" to learn options is increasingly well understood, the question of "what" good options should be has remained elusive. We formulate our answer to what "good" options should be in the bounded rationality framework (Simon, 1957) through the notion of deliberation cost. We then derive practical gradient-based learning algorithms to implement this objective. Our results in the Arcade Learning Environment (ALE) show increased performance and interpretability.
Introduction
The paper asks what makes temporal abstractions useful when reinforcement-learning agents face computation and data limits. It proposes bounded rationality and deliberation cost as criteria for learning options that support faster learning and planning.
- Temporal abstraction has been used to shorten plans, speed planning, improve generalization, support exploration, and increase robustness.
- Standard reinforcement-learning optimality assumes agents have extensive data and computation, overlooking practical resource limitations.
- Although options can accelerate policy computation, primitive actions remain sufficient for absolute optimality, making their precise theoretical benefit difficult to formalize.
- The paper uses bounded rationality to define good options as abstractions that let agents learn and plan faster.
- The proposed objective is implemented with the option-critic framework and evaluated in Atari games.
Preliminaries
The preliminaries formalize MDPs, options, and their augmented state-option process, then review actor-critic and option-critic gradients for end-to-end option learning.
- Markov Decision Processes: An MDP specifies states, actions, rewards, transitions, and discounting; policies induce a Markov process whose value functions support optimal control.
- Gradient-Based Learning: Actor-critic methods optimize parameterized policies by stochastic gradient ascent while learning action values, and option-critic extends this approach to option policies and terminations.
- Options: Options are triples containing an initiation set, an internal policy, and a termination condition, executed under call-and-return control.
- Options: Combining options with a base MDP yields an SMDP, where transitions between decision points can take random amounts of time.
- Intra-Option Bellman Equations: Intra-option Bellman equations provide the recursive structure used to derive gradient-based algorithms for learning options.
- Augmented State Space: The augmented state space pairs states with options, restoring the Markov property needed for option-level transition modeling.
- Gradient-Based Learning: The termination gradient lengthens advantageous options and makes options more likely to terminate when another option would be better.
Deliberation Cost Model
The paper models deliberation as a cost paid when switching options, motivating options that amortize computation over longer executions. It incorporates this cost into an unconstrained, gradient-based objective and explains how its parameters shape option termination and computational foresight.
- Motivation: Options are motivated as a way to use limited computational resources by allowing fast execution after deliberation and by compressing communicated intent.The paper connects this view to fast and frugal heuristics, model-based planning between options, and habitual learning within options.
- Cost model: A fixed switching cost η is paid when selecting an option, while execution within an option is free; longer options therefore reduce average cost per step.With continuation probability κ, expected discounted duration is d = 1/(1−γκ), and the average cost rate is (1−γκ)η.
- Objective: The objective maximizes expected reward while penalizing deliberation cost, replacing an expensive constrained optimization with an unconstrained Lagrangian formulation suitable for model-free learning.The regularization coefficient η scales the deliberation-cost penalty, and the transformed reward is the base reward minus that cost.
- Gradient learning: The switching-cost design represents option termination as a cost and adds a scalar margin η to the advantage function used by termination learning.This formulation yields termination gradients for the option-critic architecture under the transformed reward.
- Gradient learning: Increasing η favors maintaining options by reducing the advantage gap required for termination, allowing η to encode approximation error or uncertainty in value estimates.The resulting termination gradient tilts the balance toward continuing an option rather than terminating it.
- Computational horizon: The deliberation-cost discount factor λ truncates internal cost predictions and should match representational capacity because λ approaching 1 makes prediction harder.At λ = 0, learning considers only immediate computational cost and can lack foresight about lower long-run costs obtained through less favorable immediate costs.
Experiments
The experiments introduce A2OC, an asynchronous option-critic algorithm, and test deliberation costs in Atari environments for performance, option persistence, and interpretability. Deliberation costs reduce degenerate single-step terminations and produce specialized options that persist through trajectories.
- Algorithm: A2OC adapts the option-critic architecture to A3C-style asynchronous online learning with parallel agents.Its network shares features across option policies, termination functions, and Q-value heads.
- Experimental setup: The experiments evaluate learned options in Atari, using Amidar to analyze option policies and termination behavior qualitatively.Amidar is a grid-like game in which the agent covers ground while avoiding enemies.
- Option behavior: Without deliberation cost, options eventually terminate at every step, producing degenerate single-step behavior.The experiment compares this behavior with agents trained using deliberation costs.
- Option behavior: With deliberation cost, options persist over long contiguous trajectory segments and terminate mainly at intersections that serve as decision points.The learned options are specialized and selected in specific scenarios rather than merely being repeatedly reselected each step.
- Performance: Table 1 reports final performance across different regularization levels, with comparability limited because A3C DeepMind uses nonpublic human-start evaluation.The table contrasts those scores with results from the experiments' random-start initialization.
- Termination rates: Increasing deliberation cost η decreases average termination probabilities, whereas no cost drives termination rapidly to 100%.The tested costs range from η = 0 to η = 0.03 in increments of 0.005, although the decrease varies across environments.
Conclusion and Future Work
The paper concludes that deliberation cost encourages longer, intuitive options while retaining good performance. It also identifies broader applications of deliberation cost and directions involving missed opportunities and representational limits.
- Conclusion: Deliberation cost incentivizes options that persist longer and, in the option-critic architecture, yields good performance alongside intuitive options that do not shrink over time.The conclusion presents this as the main empirical outcome of combining deliberation cost with option-critic learning.
- Conclusion: The paper connects deliberation cost with earlier regularization notions from Mann et al. and Bacon et al.This connection is presented as part of the broader formulation of deliberation cost.
- Future work: Deliberation cost can represent bounds beyond lengthy computation, including missed opportunities and limits in estimating action values.The paper proposes these as future directions rather than established experimental results.
Appendix
The appendix includes training curves across four Atari 2600 games and termination-probability curves under varying deliberation costs. These figures examine learning over training and how cost changes option termination.
- Training curves: Figure 3 shows training curves for different deliberation costs across 4 Atari 2600 games over up to 80M frames.The figure compares learning trajectories under multiple cost settings.
- Termination probabilities: Figure 4 plots average termination probabilities during training for varying deliberation costs.With no deliberation cost, the termination rate quickly reaches 100%.