PaperlayerView exact revision on arXiv

Source-linked AI summary

Increasing the Action Gap: New Operators for Reinforcement Learning

Marc G. Bellemare, Georg Ostrovski, Arthur Guez, Philip S. Thomas, Rémi Munos

arXiv:1512.04860v1cs.AIcs.LG

TL;DR

Value-based reinforcement learning can suffer when Bellman Q-values are interpreted through nonstationary policies and then approximated or estimated. This paper introduces locally consistent, optimality-preserving operators that increase action gaps, extends them to interpolation settings, and reports improved greedy policies in a coarse bicycle domain.

  • Problem

    Bellman Q-functions can assign nongreedy values that do not represent stationary-policy returns, making greedy action selection vulnerable to estimation and approximation errors.

  • Method

    The paper introduces a consistent Bellman operator enforcing local stationarity, then develops consistent interpolation operators and broader sufficient conditions for preserving optimality.

  • Results

    The consistent operator preserves optimality, increases action gaps, and improves greedy policies in the coarse bicycle-domain interpolation experiment.

  • Takeaways & Limitations

    Increasing action gaps can improve policies derived from Q-value interpolation, especially when coarse representations make trajectories fall far from grid points.

Abstract

from arXiv · show

This paper introduces new optimality-preserving operators on Q-functions. We first describe an operator for tabular representations, the consistent Bellman operator, which incorporates a notion of local policy consistency. We show that this local consistency leads to an increase in the action gap at each state; increasing this gap, we argue, mitigates the undesirable effects of approximation and estimation errors on the induced greedy policies. This operator can also be applied to discretized continuous space and time problems, and we provide empirical results evidencing superior performance in this context. Extending the idea of a locally consistent operator, we then derive sufficient conditions for an operator to preserve optimality, leading to a family of operators which includes our consistent Bellman operator. As corollaries we provide a proof of optimality for Baird's advantage learning algorithm and derive other gap-increasing operators with interesting properties. We conclude with an empirical study on 60 Atari 2600 games illustrating the strong potential of these new operators.

Background

The paper formulates reinforcement learning over finite-action MDPs using Q-functions and value functions, with Bellman iteration producing an optimal Q-function and its induced greedy policy.

  • Background: An MDP is specified by state and action spaces, transition probabilities, rewards, and a discount factor.The action space is finite, and rewards are bounded.
  • Background: A deterministic policy’s state-conditional value is its expected discounted return from a starting state.
  • Background: The Bellman operator is a contraction whose unique fixed point is the optimal Q-function.
  • Background: A Q-function induces a greedy policy by selecting the action with the highest Q-value at each state.For the optimal Q-function, greedy and optimal actions coincide.
  • Background: The paper’s operators extend beyond the Bellman setting to SARSA, policy evaluation, fitted Q-iteration, and sample-based Q-learning analogues.

The Consistent Bellman Operator

The consistent Bellman operator addresses nonstationary interpretations of Bellman Q-values by enforcing local policy consistency, preserving optimality while increasing action gaps. Its interpolation variant is theoretically justified and empirically improves greedy policies in a coarse bicycle domain.

  • The Consistent Bellman Operator: The Bellman operator’s nongreedy components do not generally represent returns from stationary policies, creating vulnerability to Q-function estimation and approximation errors.Small perturbations can cause the greedy policy to select the wrong action.
  • The Consistent Bellman Operator: The consistent Bellman operator locally enforces stationarity by repeating an action when the process returns to the same state.In the cake example, this evaluates repeatedly eating cake until reaching the low-value state.
  • The Consistent Bellman Operator: The operator preserves the set of optimal policies while devaluing suboptimal actions, thereby increasing the action gap.It is optimality-preserving and gap-increasing, with strict gap increases possible for some state-action pairs.
  • Aggregation Methods: The consistent operator can be defined for aggregation schemes and remains applicable to deterministic kernels such as multilinear or barycentric interpolation in continuous-state MDPs.
  • Q-Value Interpolation: Unlike ordinary Q-value interpolation, consistent Q-value interpolation is optimality-preserving and gap-increasing.Ordinary Q-value interpolation remains a contraction but is not guaranteed to preserve optimality.

A Family of Convergent Operators

The paper derives weak sufficient conditions for operators to preserve optimality and increase action gaps, extending the consistent Bellman framework beyond contraction-based methods. It also establishes links to advantage learning and introduces additional operators with distinct convergence and fixed-point properties.

  • Theorem 1 characterizes optimality-preserving, gap-increasing operators using upper and lower bounds relative to the Bellman operator and current action gaps.The conditions permit subtracting up to, but not including, the current action gap from each Q-value.
  • The operator family applies to arbitrary Q-value approximation schemes, although operators in the family are generally not contractions.When Q-functions are represented exactly, the family remains optimality-preserving and gap-increasing.
  • Theorem 1 establishes convergence of dynamic-programming-like iterates without requiring contraction, a fixed point in the Q-function space, or convergence of suboptimal Q-values.The paper presents this as the first such result to its knowledge.
  • The consistent Bellman and consistent Q-value interpolation operators are optimality-preserving, and the consistent Bellman operator is also a contraction.Both consistent operators are gap-increasing under the strengthened inequality condition.
  • For α ∈ [0, 1), the advantage learning operator has a unique limit equal to the optimal value function V ∗.The paper derives this as a corollary of its optimality-preservation conditions.
  • Persistent advantage learning is designed to favor repeated actions and achieves excellent performance on Atari 2600 games, while the α-lazy operator can have multiple fixed points.The α-lazy operator updates Q-values only when doing so affects the greedy policy and remains optimality-preserving and gap-increasing.

Experimental Results on Atari 2600

The Atari experiments replace only DQN’s learning rule with advantage-based operators and evaluate them across stochastic and original settings. The operators generally improve performance and increase action gaps while producing lower, more realistic value estimates.

  • Evaluation setup: The ALE evaluation uses DQN agents with experience replay, while replacing the standard update errors with errors for the proposed operators.The operators also include parameterized variants such as persistent advantage learning.
  • Evaluation setup: Stochastic Minimal applies control stochasticity with p = 0.25, no death information, and a minimal action set, making it more challenging than previous settings.The agent selects a new action every four frames, so rejected actions create an approximate reaction delay.
  • Stochastic Minimal results: 37 of 60 games favor advantage learning over DQN, while 35 favor persistent advantage learning; both perform worse on one game.The comparison uses paired t-tests with 99% confidence intervals, and persistent advantage learning is better than advantage learning on 16 games versus 6.
  • Original DQN results: Across games in the Original DQN setting, median score improvements over DQN are 8.4% for A.L. and 9.1% for P.A.L.Average score improvements are 27.0% for A.L. and 32.5% for P.A.L.; the learning curves are described as representative rather than exceptional.
  • Action gaps and values: The proposed operators produce significantly larger action gaps than DQN and lower value estimates that better match the true value function.The comparison uses a single trajectory from a trained DQN agent playing SPACE INVADERS.

Open Questions

The paper identifies weaker optimality-preserving conditions as an open theoretical direction and raises unresolved questions about statistical efficiency and probabilistic interpretations.

  • Weaker Conditions for Optimality: Optimality may require only convergence to a Q-function whose greedy actions are optimal, without preserving the optimal value function or suboptimal Q-values.The authors note that their proof technique does not currently extend to potentially weaker conditions.
  • Statistical Efficiency of New Operators: The paper leaves open whether advantage learning has a probabilistic interpretation and whether the consistent Bellman operator can be less statistically efficient than the usual Bellman operator.The comparison concerns the probability of misclassifying the optimal action.

Concluding Remarks

The paper presents a family of optimality-preserving operators centered on increasing action gaps, with experiments showing improved performance from a simple Bellman-update modification.

  • Contributions: The family includes the consistent Bellman operator as a distinguished optimality-preserving member.The conclusion frames the family as a broader class of alternatives to the classical Bellman operator.
  • Implications: Experiments indicate that action gaps are central to greedy-policy performance over approximate value functions.The reported performance gains arise from modifying the Bellman operator rather than changing the DQN architecture.
  • Implications: The authors argue that classical Q-functions may be inadequate for producing reliable policies in practice and that revisiting value definitions can be fruitful.This conclusion also questions the traditional policy-value relationship in value-based reinforcement learning.

Appendix

The appendix contains proofs, additional Bicycle-domain experiments, and detailed Arcade Learning Environment results covering 60 games.

  • Appendix organization: The first appendix section presents proofs of the paper’s theoretical results.It is followed by experimental material rather than additional theoretical development.
  • Appendix organization: The second appendix section provides experimental details and additional results for the Bicycle domain.The appendix separates these results from the Atari experiments.
  • Appendix organization: The final appendix section details the Arcade Learning Environment experiments, including results on 60 games.These details supplement the main-text Atari evaluation.

Theoretical Results

The paper derives sufficient conditions under which modified Bellman operators preserve optimality while increasing action gaps. These results establish convergence of value iterates and include the consistent Bellman and consistent Q-value interpolation operators.

  • Sufficient conditions: Theorem 2 requires an operator to remain below the Bellman operator while not reducing each action value beyond an α-weighted action gap.The condition uses α ∈ [0, 1) and the current statewise maximum V(x).
  • Optimality preservation: Under these conditions, the iterated value sequence converges and the operator preserves optimality.The proof identifies the limiting value with V∗ through uniqueness of the Bellman fixed point.
  • Gap increase: The same sufficient conditions also make the operator gap-increasing.This follows after establishing convergence and showing that suboptimal actions remain below the optimal value.
  • Corollaries: The consistent Bellman operator and consistent Q-value interpolation Bellman operator are both optimality-preserving and gap-increasing.They are identified as corollaries of the general operator conditions.

Experimental Details: Bicycle

The bicycle experiment evaluates sample-based interpolation operators on discretized state spaces using averaging value iteration. The consistent Bellman operator reaches the goal where the ordinary Bellman operator does not, while related operators also outperform it.

  • Setup: The experiment uses a bicycle simulator with a reward function encouraging movement toward the goal.The discount factor is γ = 0.99.
  • Reward design: The original reward function is unsuitable for value iteration, so the experiment uses a related reward function instead.The paper states that the replacement was easier to work with and produced qualitatively similar results for similar reward functions.
  • Operators: The study compares sample-based Q-value interpolation and consistent Q-value interpolation Bellman operators over representative grid states.Q-value interpolation defines a Q-function over the continuous state space from the grid representation.
  • Optimization: Averaging value iteration is applied simultaneously across representative states and actions, with η = 0.1 selected as a suitable step size.The averaging form was chosen because it led to faster convergence.
  • Results: On both 8 × · · · × 8 and 10 × · · · × 10 grids, the Bellman operator fails to find the goal while the consistent Bellman operator succeeds.Advantage learning and persistent advantage learning also outperform Bellman, but appear slightly more unstable on the smaller grid.

Experimental Details: ALE

The Atari experiments evaluate the operators within DQN-based agents across multiple settings. The original DQN setting follows the reference protocol, and results are reported across 60 games.

  • Environment timing: The DQN experiments use four consecutive frames as one atomic agent time step, while each frame is a single ALE emulation step.This defines the temporal granularity of action selection and environment interaction.
  • Stochastic Minimal setting: The Stochastic Minimal setting rejects actions with probability p at each frame and repeats the previous action when rejection occurs.Because the agent selects actions every four frames, the controls approximate reaction delay.
  • Original DQN setting: The Original DQN setting averages three trials over 200 million frames, treats lost lives as termination signals, and omits stochastic controls.This setting matches the experimental protocol of Mnih et al. (2015).
  • Trajectory analysis: A separate experiment records complete episodes generated by a trained DQN using an ϵ-greedy policy with ϵ = 0.05.The recorded trajectories support subsequent value-function analysis.
  • Evaluation coverage: The study reports results for 60 games, including five games not included in the comparison table of Bellemare et al. (2013).Those five games are marked with a dagger in Table 1.

DQN Implementation Details

The DQN implementation uses the target network, rather than the policy network, to compute correction terms for the advantage-based operators. Using the policy network instead produced worse performance.

  • Target-network usage: Correction terms for ΔALQ and ΔPALQ are computed with DQN’s target network, including the added correction term.The target network is updated every 10,000 time steps.
  • Implementation comparison: The operators perform worse when the correction term is computed from the policy network instead.This implementation comparison motivates using the target network for the correction terms.

Parameter Selection

The α parameter was selected by sweeping seven values on five Atari games and manually choosing the value with the best highest achieved score. α = 1.0 violates the theorem’s conditions, while α = 0.0 corresponds to DQN.

  • Sweep design: Seven α values were evaluated on ASTERIX, BEAM RIDER, PONG, SEAQUEST, and SPACE INVADERS using each agent’s highest achieved score.The tested values were α ∈ {0.0, 0.1, 0.3, 0.5, 0.7, 0.9, 1.0}.
  • Selection rule: The α value for each operator was manually selected as the one that seemed to achieve the best performance.
  • Reference point: α = 0.0 corresponds to DQN for both operators.
  • Theoretical constraint: α = 1.0 does not satisfy the theorem’s conditions.
  • Observed anomaly: Seaquest agents using Persistent Advantage Learning with α = 0.9 showed unusual performance attributed to a statistical issue.
Loading 1512.04860v1…