Source-linked AI summary
The Option-Critic Architecture
Pierre-Luc Bacon, Jean Harb, Doina Precup
TL;DR
Autonomously discovering temporally extended actions remains challenging, especially when subgoal-based approaches are costly to scale. The paper derives policy-gradient theorems and introduces an option-critic architecture that jointly learns option policies, termination conditions, and the policy over options. Experiments report flexible end-to-end learning without requiring subgoals or additional rewards, including successful learning within a single task without slowdown and benefits for transfer learning.
Problem
Existing approaches commonly discover subgoals and then learn policies for them, which can create combinatorial scaling and task-sized data and computation costs.
Method
The option-critic architecture jointly learns intra-option policies, termination functions, and the policy over options using policy-gradient theorems.
Results
The approach successfully learns options within a single task without slowdown while providing benefits for transfer learning.
Takeaways & Limitations
Option learning can be performed end to end by specifying only the number of options, without subgoals, extra rewards, demonstrations, or multiple problems.
Takeaways & Limitations
The framework assumes that all options apply everywhere, while learning initiation sets would require additional constraints and may add computational cost.
Abstract
from arXiv · showhide
Temporal abstraction is key to scaling up learning and planning in reinforcement learning. While planning with temporally extended actions is well understood, creating such abstractions autonomously from data has remained challenging. We tackle this problem in the framework of options [Sutton, Precup & Singh, 1999; Precup, 2000]. We derive policy gradient theorems for options and propose a new option-critic architecture capable of learning both the internal policies and the termination conditions of options, in tandem with the policy over options, and without the need to provide any additional rewards or subgoals. Experimental results in both discrete and continuous environments showcase the flexibility and efficiency of the framework.
Introduction
The paper frames autonomous discovery of temporal abstractions as a scaling challenge and introduces an end-to-end alternative based on jointly learning options and their components. The approach requires only the number of desired options and targets effective learning across task settings.
- Motivation: Existing option-discovery methods often find subgoals first, creating combinatorial scaling difficulties and potentially task-sized data and computation costs.The worst case can be as expensive as solving the entire task.
- Approach: The paper derives policy-gradient results that jointly learn intra-option policies, termination functions, and the policy over options.This blurs the distinction between discovering options and learning them.
- Approach: The framework supports linear and nonlinear function approximators across discrete and continuous state-action spaces.The paper positions this flexibility as part of the approach’s generality.
- Reported outcome: The authors report successful single-task option learning without slowdown while retaining benefits for transfer learning.This contrasts with methods whose advantages come substantially from reusing options across similar tasks.
- Requirements: The method learns meaningful temporally extended behaviors without requiring subgoals, extra rewards, demonstrations, or multiple problems.Only the number of desired options must be specified, although pseudo-rewards can be used if desired.
Preliminaries and Notation
The preliminaries define the MDP, policy-gradient, and options frameworks used by the paper. They establish discounted state weighting and describe options as temporally extended actions represented within a semi-Markov decision process.
- Markov decision processes: An MDP comprises states, actions, transition dynamics, and a reward function, with policies mapping states to action distributions.The paper develops the main ideas for discrete spaces while noting extensions to continuous spaces.
- Policy gradients: Policy-gradient methods optimize a performance objective over parametrized stochastic policies using stochastic gradient descent.The policy-gradient theorem provides objective gradients with respect to policy parameters.
- Policy gradients: The discounted state distribution weights states by γ^t along trajectories from the designated start state.This weighting underlies the discounted policy-gradient formulation.
- Options: An option is a triple of an initiation set, an intra-option policy, and a termination function.The options framework turns an MDP with options into a semi-Markov decision process.
- Options: Intra-option learning exploits the underlying MDP to learn about multiple options in parallel.The paper uses this property in its approach.
Learning Options
The option-critic approach jointly learns intra-option policies and termination functions with the policy over options by optimizing the current task’s expected return. It derives policy-gradient results that connect local option changes to global performance and interpret termination through option advantage.
- Learning setup: The method continually distills experience into the value function, policy over options, intra-option policies, and termination functions.Policy and termination components are represented with differentiable parameterized function approximators.
- Option execution: Under call-and-return execution, the agent follows an option’s intra-option policy until its termination function ends the option, then selects another option.The policy over options chooses the next option only at termination.
- Objective: The objective is expected discounted return from a designated state and initial option, depending jointly on the policy over options, intra-option policies, and termination functions.The derivation takes gradients with respect to the intra-option policy and termination parameters.
- Policy gradients: The intra-option policy gradient theorem describes how local primitive-action changes affect the global expected discounted return.Unlike subgoal or pseudo-reward methods, the derivation accounts for how changes propagate through the overall objective.
- Termination gradients: The termination gradient theorem uses the option advantage: negative advantage increases termination likelihood when continuing the current option is worse than the expected value over options.The termination gradient is evaluated through the arrival-value function and uses a state-option weighting shifted by one time step.
Algorithms and Architecture
The option-critic architecture combines an actor containing option policies and termination functions with a critic over option values and advantages. Its learning algorithm uses stochastic gradient updates, while practical variants avoid separately learning redundant action-option values.
- Learning algorithm: A two-timescale algorithm learns values quickly while updating intra-option policies and termination functions more slowly.The updates are based on the intra-option policy and termination gradient theorems.
- Architecture: The option-critic architecture places intra-option policies, termination functions, and the policy over options in the actor, with QΩ and AΩ in the critic.The policy over options can be obtained through policy gradients, planning, or temporal-difference updates.
- Implementation: The tabular prototype uses intra-option Q-learning with separate learning rates for the critic, intra-option policies, and termination functions.The algorithm evaluates options, samples actions from the current intra-option policy, and selects a new option after termination.
- Practical estimation: Learning only QΩ and deriving QU avoids the computational cost of separately learning both action-option and option values.QU is expressed as an expectation over next states of the immediate reward plus the discounted arrival value.
- Experiments: In deep neural-network experiments, the proposed estimator was used in the Arcade Learning Environment.
Experiments
Experiments show that option-critic learns temporally extended behaviors autonomously across discrete, continuous, and visual environments, while adapting effectively to changed goals and complex tasks.
- Four-Rooms: After 1000 episodes, option-critic recovered faster than primitive actor-critic and SARSA(0) after the four-rooms goal moved randomly.The comparison averaged each learning curve over 350 runs.
- Four-Rooms: The four-rooms options were learned from scratch at a rate comparable to primitive methods while retaining recovery benefits after the goal change.The experiment evaluated options learned fully autonomously rather than specified in advance.
- Pinball: By 40 episodes, near-optimal options had been learned in all Pinball settings with 2, 3, or 4 options.Successful trajectories showed temporal extension and specialization, including consistent use of one option near the goal.
- Arcade Learning Environment: The deep architecture shared a convolutional representation across intra-option policies, termination functions, and the policy over options.It concatenated the last four images before convolutional processing and used linear-softmax policies with sigmoid terminations.
- Arcade Learning Environment: A baseline in the intra-option policy-gradient estimator improved action-distribution quality and overall agent performance in Seaquest.The baseline was added to reduce estimator variance; without it, intra-option policies tended to become more deterministic.
- Arcade Learning Environment: Within 200 episodes, eight end-to-end learned options achieved the goal in all four Arcade Learning Environment games, surpassing primitive-action DQN in Asterisk, Seaquest, and Zaxxon.The same parameter configuration was used across all four games, without predefined subgoals or pseudo-rewards.
- Arcade Learning Environment: With two options in Seaquest, the learned solution specialized one option around upward behavior and the other around downward behavior.The resulting option structure was easy to interpret and included transitions from one directional behavior to the other.
Related Work
Related approaches learn options through termination optimization, hidden-variable estimation, open-loop macro-actions, or intrinsic rewards and supplied subgoals. Option-critic instead provides a general gradient-based framework that does not require intrinsic motivation for learning options.
- Existing option-discovery approaches: Prior work optimized termination functions with gradient methods or learned them as hidden variables using expectation-maximization.These approaches addressed option discovery through distinct termination-learning formulations.
- Existing option-discovery approaches: Other methods learned open-loop intra-option policies, also called macro-actions, using action sequences in a planning-style formulation.The related approach focuses on fixed or open-loop action sequences rather than the option-critic formulation.
- Experimental comparison: The Arcade Learning Environment experiments used the same parameter set across four games, including eight options and regularization terms.The figure caption specifies 0.01 termination regularization, 0.01 entropy regularization, and a baseline for intra-option policy gradients.
- Comparison with DQN-based option learning: A DQN-based gradient option learner used intrinsic rewards for internal policies and extrinsic rewards for the policy over options, with subgoal descriptions supplied as inputs.Option-critic differs by not requiring intrinsic motivation or supplied subgoal descriptions.
Discussion
The option-critic framework jointly learns intra-option policies, termination functions, and the policy over options for the current task. Its main limitations are biased discounted gradient estimators and the assumption that all options apply everywhere.
- The framework jointly learns intra-option policies, termination functions, and the policy over options to optimize the task’s performance objective.
- Unbiased gradient estimates are possible by adding γ^t Q_t factors, but their sample complexity is generally too high.
- The biased gradient estimators performed well in the reported experiments despite the discounted-case bias.
- The framework’s biggest remaining limitation is assuming that all options apply everywhere.
- Learning initiation sets would require an ergodic augmented state-option chain, while their precise flow condition and sparsity regularization remain future work.
Augmented Process
The augmented process tracks states together with options and defines discounted transitions for option execution. These transitions are extended recursively to multiple steps.
- When an option is initiated or executing, the process defines the discounted transition probability to the next state-option pair.
- Conditioning on the preceding state and option gives the discounted probability of transitioning to the next state and current option.
- The augmented process expresses k-step discounted transition probabilities recursively.
Proof of the Intra-Option Policy Gradient Theorem
The intra-option policy-gradient proof differentiates the option-value function and uses a recursion to obtain the gradient of the expected discounted return with respect to policy parameters.
- The proof begins by taking the gradient of the option-value function.
- Because θ appears only in the intra-option policies, the derivative follows from that parameterization assumption.
- Substituting the derivative into the preceding expression and using the augmented process yields a recursion.
- The resulting recursion gives the gradient of the expected discounted return with respect to θ.
Proof of the Termination Gradient Theorem
The termination-gradient proof starts from the expected discounted reward, expands the option-value expression, and differentiates it using the augmented-process structure.
- The proof defines the expected discounted reward from an initial state-option pair.
- The gradient of U is derived from this expansion.
- The structure of the augmented process is used to continue the termination-gradient derivation.