PaperlayerView exact revision on arXiv

Source-linked AI summary

VA-learning as a more efficient alternative to Q-learning

Yunhao Tang, Rémi Munos, Mark Rowland, Michal Valko

arXiv:2305.18161v2cs.LGstat.ML

TL;DR

Learning advantage directly is difficult because it lacks the recursive equation needed for standalone bootstrapping. VA-learning learns a value function alongside advantage, and the paper reports improved sample efficiency over Q-learning across tabular and deep RL settings. Its connection to dueling architectures also offers a potential explanation for why a simple DQN architecture change helps.

  • Problem

    Although advantage measures relative performance between actions, unlike Q-functions it lacks a recursive equation for standalone bootstrapping.

    Source: §1 · p. 1

  • Method

    VA-learning directly learns a value function and an advantage function together, with the value function adapted to the data-collection policy.

    Source: §1 · p. 1, §7 · p. 9

  • Results

    VA-learning makes more efficient use of finite samples and performs better empirically than Q-learning in tabular and deep RL settings.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The paper connects VA-learning to behavior dueling, generalizes dueling as a special case, and suggests this may explain why a simple DQN architecture change helps.

    Source: §7 · p. 9

    VA-learning’s decomposition assumes value sharing across actions is useful; when within-state Q-gaps greatly exceed between-state value gaps, learning action values separately may be better.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

In reinforcement learning, the advantage function is critical for policy improvement, but is often extracted from a learned Q-function. A natural question is: Why not learn the advantage function directly? In this work, we introduce VA-learning, which directly learns advantage function and value function using bootstrapping, without explicit reference to Q-functions. VA-learning learns off-policy and enjoys similar theoretical guarantees as Q-learning. Thanks to the direct learning of advantage function and value function, VA-learning improves the sample efficiency over Q-learning both in tabular implementations and deep RL agents on Atari-57 games. We also identify a close connection between VA-learning and the dueling architecture, which partially explains why a simple architectural change to DQN agents tends to improve performance.

1. Introduction

VA-learning addresses the difficulty of learning advantage directly by learning a value function alongside it, with theoretical guarantees and reported efficiency gains over Q-learning. It also connects to dueling architectures and improves Atari-57 performance over dueling and Q-learning baselines.

Large-scale value-based learning

  • Direct advantage learning matters because advantage measures relative action performance but, unlike Q-functions, has no recursive equation for standalone bootstrapping.Q-learning itself updates predictions by bootstrapping from future value predictions.Source: §1 · p. 1
  • VA-learning directly learns V and A together, using a value function adapted to the data-collection policy rather than learning advantage only through Q.The paper relates this approach to dueling, which decomposes Q through its parameterization while running vanilla Q-learning.Source: §1 · p. 1

Theoretical guarantee as Q-learning

  • VA-learning’s implied Q-function converges to the same target fixed point as Q-learning, while V and A converge to their respective value and advantage functions.The introduction presents this as a theoretical guarantee comparable to Q-learning’s.Source: §1 · pp. 1–2

Improved efficiency of tabular algorithms

  • The Q = V + A decomposition lets the shared value component be learned faster than the action-specific advantage; bootstrapped targets strengthen the efficiency gain in tabular MDPs.The paper attributes the faster learning of V to its being shared across actions.Source: §1 · pp. 1–2

Large-scale value-based learning

  • VA-learning generally outperforms vanilla Q-learning in tabular and deep RL, with robust improvements over dueling and Q-learning on Atari-57.The Atari comparison is reported on the Atari-57 game suite.Source: §1 · pp. 1–2

2. Background

The background defines an MDP and its policy-dependent value quantities, then frames policy evaluation and control as Bellman recursions. Since exact recursions require transition and reward knowledge, learning instead uses sampled transitions.

Background

  • An MDP is specified by finite state and action spaces, reward and transition kernels, and a discount factor.The passage introduces Q-functions among the important quantities for a policy.Source: §2 · p. 2
  • For a policy, the value function averages action values, and the advantage function is the action value minus the state value.These definitions distinguish state-level value from action-relative value.Source: §2 · p. 2
  • Policy evaluation applies the Bellman evaluation recursion toward Qπ, while control applies the Bellman control recursion toward Q⋆.Control seeks an optimal policy that maximizes Q⋆ over actions.Source: §2 · p. 2
  • Because exact recursions require analytic transition and reward knowledge, the setup uses sampled transition tuples; the behavior policy is fixed and covers every state-action pair.The algorithm fragment samples a transition, forms Q as V + A, computes a backup target, and updates the iterates.Source: §2 · p. 2
  • Under mild data-process assumptions, TD-learning and Q-learning converge almost surely to Qπ and Q⋆, respectively.The passage attributes these convergence results to prior work.Source: §2 · p. 2

3. VA-learning

VA-learning learns value and advantage estimates directly, combining them to recover a Q-function. The section explains how shared value estimates can speed learning, gives convergence results, and describes a function-approximation implementation.

3. VA-learning

  • VA-learning maintains V and A rather than a separate Q estimate, combines them to recover Q, and uses a shared backup target for value and advantage updates.The advantage parameterization has zero mean under behavior policy μ and is described as reminiscent of, but distinct from, dueling.Source: §3 · p. 2, §3.1 · p. 3

3.2. Why VA-learning can be more efficient

  • When only action a has been sampled at state y, the shared V(y) can still inform bootstrapping from Q(y,b), potentially improving the target at preceding state x.Q-learning's estimate for Q(y,b) remains unupdated until that action is sampled; VA-learning updates V(y) along with A(y,a).Source: §3.2 · pp. 3–4
  • VA-learning significantly improves convergence speed and asymptotic accuracy over Q-learning in tabular policy evaluation; Figure 2 also reports new variants outperforming prior methods.Figure 2 compares VA-learning, Q-learning with behavior dueling, Q-learning with uniform dueling, and regular Q-learning on tabular MDPs.Source: §3.2 · p. 4, Figure 2 · p. 4
  • Sharing V across actions may be less useful when within-state Q-value gaps greatly exceed between-state value gaps; separately learning action values may then be better.The text says sharing values across actions should generally be useful in many practical scenarios, but does not claim it always is.Source: §3.2 · p. 4

3.3. Convergence of VA-learning

  • The VA recursion converges to the target Q-function for both policy evaluation and control, with the implied Q error decreasing as O(γ^t).The value and advantage estimates are also described as converging geometrically.Source: §3.3 · p. 4
  • The implied Q-function converges to the target Q-function, while V and A converge to functions corresponding to following behavior policy μ first, then target policy π.Sample-based VA-learning converges to these fixed points under regular assumptions on the data process and learning rate.Source: §3.3 · p. 5

3.4. VA-learning with function approximation

  • With function approximation, separate parameterized value and advantage functions are summed into Q, and slowly updated target networks support construction of the update targets.The algorithm also estimates the behavior policy from observed transitions when it is unknown.Source: §3.4 · p. 5

4. Behavior dueling architecture

Behavior dueling centers the advantage function under the behavior policy, making regular dueling its uniform-policy special case. Its parameterization shares value information across actions, though its advantage updates differ from VA-learning’s.

4. Behavior dueling architecture

  • Behavior dueling parameterizes advantages to have zero mean under the behavior policy; regular dueling is the special case with a uniform policy.The construction subtracts the behavior-policy-weighted average of an unconstrained action function.Source: §4 · pp. 5–6

4.1. Connections between VA-learning and Q-learning with behavior dueling

  • With behavior dueling, Q-learning’s value update fits a value target, while its advantage updates couple actions unlike VA-learning’s separate action-wise updates.When one action is taken, the parameterization also updates the advantage for other actions.Source: §4.1 · p. 6

4.2. Why behavior dueling is better than dueling

  • The authors hypothesize that centering advantages under the behavior policy improves value sharing; this choice minimizes unshared advantage components and may speed downstream learning.They contrast behavior dueling with uniform dueling, which assumes the behavior policy is uniform.Source: §4.2 · pp. 6–7

5. Discussion of prior work

The discussion distinguishes VA-learning from related advantage-learning methods and connects dueling to over-parameterized function approximation. It also identifies off-policy stability of dueling as an open question.

Advantage learning

  • Unlike advantage learning, VA-learning targets the original Q-function; advantage learning instead enlarges value gaps between actions.In policy evaluation, advantage learning’s converged Q-function gap grows as β approaches 1.Source: §5 · p. 7
  • VA-learning subtracts the behavior-policy average Q-value at the next state, unlike gap-increasing backups, preserving Qπ as its fixed point.The text suggests combining VA-learning with gap-increasing learning as future work.Source: §5 · p. 7

Direct advantage learning

  • Direct advantage learning by Pan et al. (2021) uses Monte Carlo returns, is so far on-policy, and does not support bootstrapping out of the box.Combining that approach with VA-learning is proposed as a future direction.Source: §5 · p. 7

RL with over-parameterized linear function approximation

  • Tabular dueling is a special case of over-parameterized linear function approximation; its extra degree of freedom can share value across actions and usually speed convergence.Off-policy stability of the dueling parameterization remains an open question.Source: §5 · p. 7

6. Experiments

In full-action Atari, VA-learning and behavior dueling outperform uniform dueling and are least affected by the larger action set; restricted-action Atari results also favor them over the baselines. In tabular MDPs, Q-learning with dueling catches up as behavior approaches uniform.

6.1. Tabular MDP experiments

  • The tabular experiments compare algorithm variants under a behavior policy mixing uniform and fixed deterministic policies, measuring final performance across 20 independent runs.The reported statistic is the mean and standard deviation across runs.Source: §6.1 · p. 7
  • As the tabular behavior policy approaches uniform, Q-learning with dueling catches up in performance with behavior dueling and VA-learning.The figure varies the mixture coefficient ϵ between a uniform policy and a fixed deterministic policy.Source: Figure 3 · p. 8

6.2. Deep reinforcement learning experiments

  • VA-learning and behavior dueling significantly outperform uniform dueling on full-action Atari, which further improves over the n-step Q-learning baseline.With the full action set, VA-learning and behavior dueling are least affected by increased action count; almost all variants reach similar asymptotic performance, but learning is generally slower.Source: Figure 4 · p. 8, §6.2 · p. 8
  • On restricted-action Atari games, behavior dueling and VA-learning improve over both dueling and Q-learning baselines.This setting gives the agent only a small subset of each game’s full action set.Source: §6.2 · p. 8

7. Conclusion

The conclusion presents VA-learning as an alternative to Q-learning that learns behavior-policy-adapted value and advantage functions. It reports improved finite-sample efficiency and empirical performance, and relates VA-learning to behavior dueling.

7. Conclusion

  • The paper develops VA-learning as an alternative value-based reinforcement-learning algorithm to classic Q-learning.Source: §7 · p. 8
  • VA-learning aims to learn value and advantage functions adapted to the behavior policy and makes more efficient use of finite samples than Q-learning.The paper reports better empirical performance in both tabular and deep RL settings.Source: §7 · p. 9
  • Behavior dueling generalizes dueling as a special case and may explain why a simple architectural change improves DQN performance.Source: §7 · p. 9

A. Proof of theoretical results

The proof analyzes VA-learning by relating its value and advantage updates to Bellman backups. The resulting estimates converge geometrically, and the implied Q-function converges at a geometric rate.

A. Proof of theoretical results

  • The value update in expectation averages the Bellman backup targets across actions, while the advantage update learns the residual after subtracting the value baseline.The proof expresses the value update as an action-average of T^π applied to the residual Q estimate, and says the advantage update follows by the same argument.Source: A. Proof of theoretical results · p. 10
  • The value and advantage estimates converge geometrically in both policy evaluation and optimal control.The optimal-control argument uses the γ-contractive operator T, whose unique fixed point is Q⋆.Source: A. Proof of theoretical results · pp. 10–11
  • The implied Q estimate converges at rate O(γ^t) in policy evaluation and optimal control.For policy evaluation, the stated bound is ∥Q_t − Q^π∥∞ = O(γ^t); the control proof likewise invokes contraction toward Q⋆.Source: A. Proof of theoretical results · pp. 10–11
  • For policy evaluation, the residual estimate eQ_t = Q_t − μA_t converges geometrically to Q^π because T^π is γ-contractive with Q^π as its unique fixed point.The proof uses the contraction property of T^π to establish the convergence claim.Source: A. Proof of theoretical results · p. 10

B. Convergence of VA-learning

The stochastic-approximation analysis establishes almost-sure convergence of VA-learning under a boundedness assumption and a specified sampling setup. The appendix also points readers to the main paper for further experiment details.

B. Convergence of VA-learning

  • The convergence result assumes a uniformly bounded sequence of iterates and gives almost-sure convergence for policy evaluation.The update samples an action from μ and its reward and next-state transition at every state, with updates carried out across all states simultaneously.Source: B. Convergence of VA-learning · p. 11
  • The stochastic-approximation result uses a conventional proof extension of techniques for Q-learning and TD-learning.The cited classic proof technique is attributed to Watkins and Dayan (1992).Source: B. Convergence of VA-learning · p. 11

C. Experiment details and extra results

C.1. Tabular experiments

The tabular experiments report more accurate advantage estimates at any data budget and slightly faster Q-function approximation for VA-learning than for Q-learning. The accompanying deep-RL details describe the DQN setup and implementation choices, including an online-network baseline for VA advantage targets.

C.1. Tabular experiments

  • The tabular experiments use randomly generated MDPs with 20 states, 5 actions, and discount factor γ = 0.99.Updates use tabular parameterizations, a constant learning rate α_t = 0.1, and target parameters copied every τ = 10 updates.Source: §C.1 · pp. 11–12
  • At any data budget, VA-learning obtains more accurate advantage approximations than Q-learning and a slightly faster rate of Q-function approximation.The Q-function error comparison is reported as a complementary result to Figure 2.Source: §C.1 · p. 12, Figure 5 · p. 12
  • Policy-evaluation advantage error is measured against the target policy, with VA-learning estimating A directly and Q-learning estimating it as Q_t − πQ_t.The policy-evaluation trajectories are collected under the uniform behavior policy.Source: §C.1 · p. 12

C.2. Deep RL experiment details

  • The deep-RL experiments use DQN on Atari-57 with double Q-learning and n-step bootstrapping, setting n = 5.The passage reports that smaller n does not fully benefit from multi-step bootstrapping, while larger n can suffer from lack of off-policy corrections.Source: §C.2 · p. 13
  • For VA-learning, behavior dueling, and uniform dueling, the reported best learning rate is 1.5 · 10^-5, below the n-step Q-learning rate of 5 · 10^-5.The learning rates were selected by grid search on a subset of games.Source: §C.2 · p. 13
  • In deep VA-learning, using the online network as the baseline for the advantage backup makes VA-learning and behavior dueling more similar in practice.The passage says this implementation choice is important for calculating the advantage-function backup target.Source: §C.2 · p. 14

C.3. Deep RL experiments extra results

On Atari, VA-learning and behavior dueling improve over dueling and n-step Q-learning in most per-game comparisons, with additional robustness under changed data distributions. The paper relates VA-learning to behavior dueling through their value and advantage updates, while noting differences in their advantage gradients.

C.3. Deep RL experiments extra results

  • With greater off-policyness, VA-learning and behavior dueling gain significantly over dueling, while dueling improves on baseline Q-learning.The setting raises the final ϵ-greedy exploration rate to ϵ_f = 0.5.Source: §C.3 · p. 14
  • The comparison suggests that explicitly learning the behavior policy may be valuable relative to dueling’s implicit uniform-policy assumption.Source: §C.3 · p. 14
  • VA-learning and behavior dueling improve over dueling and n-step Q-learning with statistical significance in most full-action Atari game comparisons.In the restricted-action setup, they also show marginal performance improvements over the dueling architecture.Source: §C.3 · p. 14, Figure 6 · p. 15

D. Connections between behavior dueling and VA-learning

  • The connection analysis characterizes behavior dueling as a Q-function parameterization with the behavior-policy mean advantage subtracted.The stated parameterization is Q_θ,ϕ(x, a) = V_θ(x) + A_ϕ(x, a) − A_ϕ(x, μ).Source: D. Connections between behavior… · p. 15

D.2. Advantage gradient

  • Their advantage gradients differ, although both updates can be interpreted as fitting advantage-function components.The value estimate fits the average backup target, while the advantage estimate fits its residual after subtracting the value baseline.Source: D. Connections between behavior… · p. 15, §D.2 · p. 16

D.1. Value gradient

  • VA-learning and behavior dueling have equal expected value gradients when the target and online networks are the same.The analysis also reports equality in expectation between VA-learning and TD-learning with behavior dueling.Source: §D.1 · pp. 15–16

D.3. Why behavior dueling is better than dueling

The behavior-policy distribution uniquely minimizes the weighted squared advantage norm across parameterizations, explaining why behavior dueling reduces unshared information across actions. Across 20 randomly generated MDPs, it has a lower squared advantage norm than uniform dueling.

D.3. Why behavior dueling is better than dueling

  • Across all parameterizations, ν = µ uniquely minimizes the weighted squared norm, although the minimizer for a fixed f need not be unique.Equality is attained when f(x, ν) equals the behavior-policy expectation of f(x, a).Source: §D.3 · p. 17
  • Because ν = µ minimizes that norm, behavior dueling minimizes unshared information across actions and hence maximizes shared components.The squared norm is used as an objective for the unshared components of Q-functions.Source: §D.3 · p. 17
  • Across 20 randomly generated MDPs, behavior dueling has a lower squared advantage norm than uniform dueling during training.The comparison measures the advantage norm weighted by behavior-policy samples.Source: §D.3 · p. 17, Figure 7 · p. 18
Loading 2305.18161v2…