PaperlayerView exact revision on arXiv

Source-linked AI summary

Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition

Zihan Zhang, Yuan Zhou, Xiangyang Ji

arXiv:2004.10019v2cs.LGcs.DSstat.ML

TL;DR

The paper studies whether model-free reinforcement learning can achieve model-based learning efficiency in finite-horizon episodic MDPs without comparable complexity. It introduces UCB-ADVANTAGE using reference-advantage decomposition and proves near-optimal regret, low switching cost, and applicability to concurrent reinforcement learning. The method's scope includes tabular episodic MDPs and must integrate reference-value learning because some states may be difficult to reach.

  • Problem

    The paper asks whether model-free algorithms can match model-based learning efficiency while retaining lower time and space complexity.

  • Method

    UCB-ADVANTAGE is a model-free Q-learning variant that uses reference-advantage decomposition and stage-based updates.

  • Results

    UCB-ADVANTAGE achieves regret of ˜O(H^2SAT), matching the order of the best model-based algorithms and the information-theoretic lower bound up to logarithmic factors.

  • Takeaways & Limitations

    The results support that model-free algorithms can learn as efficiently as model-based algorithms in episodic tabular MDPs while using lower stated time and space complexity.

  • Takeaways & Limitations

    The analysis concerns episodic tabular MDPs and must integrate reference-value learning because some states may be almost unreachable.

Abstract

from arXiv · show

We study the reinforcement learning problem in the setting of finite-horizon episodic Markov Decision Processes (MDPs) with $S$ states, $A$ actions, and episode length $H$. We propose a model-free algorithm UCB-Advantage and prove that it achieves $\tilde{O}(\sqrt{H^2SAT})$ regret where $T = KH$ and $K$ is the number of episodes to play. Our regret bound improves upon the results of [Jin et al., 2018] and matches the best known model-based algorithms as well as the information theoretic lower bound up to logarithmic factors. We also show that UCB-Advantage achieves low local switching cost and applies to concurrent reinforcement learning, improving upon the recent results of [Bai et al., 2019].

1 Introduction

The paper asks whether model-free reinforcement learning can match model-based learning efficiency while retaining lower complexity, and answers affirmatively for episodic tabular MDPs. UCB-ADVANTAGE closes the regret gap, reduces switching costs, and extends to concurrent reinforcement learning.

  • Motivation: Model-free algorithms are generally more space- and time-efficient than model-based methods, motivating whether they can achieve comparable learning efficiency.The paper frames this as an open question for finite-horizon episodic tabular MDPs.
  • Approach: UCB-ADVANTAGE is a model-free Q-learning variant that uses reference-advantage decomposition and stage-based updates.The decomposition separates the optimal value into a reference component and an advantage component, learned from designed data subsets.
  • Regret: Regret is bounded by ˜O(H^2SAT), matching the order of the best model-based algorithms and the information-theoretic lower bound up to logarithmic factors.The bound holds with high probability when T exceeds a polynomial in S, A, and H, with logarithmic factors hidden.
  • Regret: The algorithm improves on UCB-Bernstein by saving a factor of H in regret up to logarithmic factors while retaining O(T) time and O(SAH) space complexity.The cited model-based comparisons use ˜O(TS^2A) time and O(S^2AH) space.
  • Switching and concurrency: UCB-ADVANTAGE has local switching cost O(SAH^2 log T), improving both regret and switching cost relative to prior work.The stage-based framework reduces the frequency of policy updates.
  • Switching and concurrency: The method applies to concurrent reinforcement learning, requiring ˜O(H^2SA + H^3SA/(ε^2M)) concurrent episodes and achieving an optimality result up to logarithmic factors in the single-threaded case.For M=1, the paper gives a matching Ω(H^3SA/ε^2) episode lower bound up to logarithmic factors.

2 Preliminaries

The paper studies finite-horizon episodic MDPs with deterministic rewards, potentially adversarial initial states, and transitions across H steps. Learning proceeds over K episodes, totaling T = KH interaction steps, with regret defined against optimal policies.

  • MDP setting: The episodic MDP is specified by S states, A actions, horizon H, transition probabilities P, and deterministic rewards r.Rewards lie in [0,1], and the setting also extends readily to stochastic rewards.
  • Interaction protocol: At each episode, the agent receives an initial state and follows a policy for H steps before the episode terminates.At step h, action a_h induces the next state through P_h(·|s_h,a_h).
  • Policies and values: A policy maps states and time indices to actions, and deterministic policies suffice because an optimal value function can be achieved by one.The paper defines value and Q-functions for policies and the optimal value recursively.
  • Scope: The analysis does not address the stronger adaptive-adversary setting, where initial states can depend on observed execution trajectories.The paper adopts the weaker oblivious-adversary model used in related work.
  • Objective: The learning problem contains K episodes and T = KH total time steps, with the objective of minimizing cumulative regret.The initial state may be selected by an oblivious adversary that knows the algorithm but not its execution trajectories.

3 The UCB-ADVANTAGE Algorithm

UCB-ADVANTAGE combines exponentially growing stages with a reference-advantage decomposition to improve Q-function estimation. The design uses all samples for a fixed reference component while restricting advantage estimation to recent-stage data, reducing updates and local switching costs.

  • Stages and updates: Stage lengths grow roughly exponentially with rate 1 + 1/H, and Q-values are updated when visits reach stage endpoints.Only samples from the latest stage enter the stage-based update framework.
  • Computational and switching properties: The stage-based framework reduces Q-function updates, thereby lowering local switching costs, and makes it easier to combine standard and advantage-based updates.The paper contrasts it with the more conservative lazy-update growth rate proposed by Bai et al. (2019).
  • Standard update limitation: The standard update rule is limited because earlier samples use outdated value estimates, so the algorithm restricts the corresponding estimate to roughly the latest 1/H fraction of data.This restriction contributes to the extra H factor in the earlier UCB-Bernstein analysis.
  • Reference-advantage decomposition: UCB-ADVANTAGE decomposes V* into a reference value V_ref and an advantage component V* − V_ref, then learns the corresponding Q-function parts separately.The reference component is an approximate optimal value function, while the advantage captures the residual.
  • Advantage-based update: The advantage-based rule estimates the fixed reference term using all collected samples while estimating the residual term from recent-stage samples.Because the residual is bounded by β, recent-stage estimation can remain accurate despite using fewer samples.
  • Reference learning: Learning V_ref inside the main algorithm is necessary because some states, especially nearly unreachable ones, cannot always be learned separately.The target reference accuracy β is independent of T and K, but integrating reference learning requires additional analysis.

4 The Analysis (Proof of Theorem 1)

The analysis establishes high-probability control of optimistic Q-values, reference-value accuracy, and the cumulative regret decomposition. These ingredients combine to prove the theorem under the paper’s stage-based and reference-advantage updates.

  • Optimism: With high probability, the learned Q-function upper bounds the optimal Q-function throughout the algorithm.The result follows from Proposition 4 and martingale concentration arguments.
  • Reference accuracy: The reference-value analysis guarantees that sufficiently visited states have reference estimates within β of their optimal values.This conclusion is obtained by combining Lemma 5 with the monotonicity of the value estimates.
  • Regret decomposition: The regret proof conditions on successful concentration events and decomposes regret into terms controlled by reference estimation, stage structure, and update errors.The proof introduces a final reference vector and bounds the resulting components using the preceding propositions and lemmas.
  • Stage-counting argument: The proof bounds stage-related sums by grouping episodes according to stage membership and iterating the resulting argument across all H levels.The counting argument uses the growth of stage lengths to control how often each stage-related quantity contributes.
  • Theorem assembly: The main theorem follows by combining Proposition 4, Lemma 5, the intermediate bound in (18), and Lemma 7 under a high-probability event.The cited passages state the combination step but do not expose the complete displayed regret expression.

Appendices

The appendices supply concentration inequalities and supporting lemmas used by the regret analysis. They rely on martingale bounds, union bounds, and elementary inequalities for weighted sums.

  • Azuma-Hoeffding: Azuma-Hoeffding bounds deviations of a martingale with bounded increments by an exponential tail probability.The appendix states the inequality for arbitrary positive integer horizons and error thresholds.
  • Freedman inequality: Freedman’s inequality controls martingale deviations using both bounded increments and conditional variance.The stated event bounds the probability that the martingale exceeds x while its variance process remains at most y.
  • Derived concentration lemma: A second martingale lemma combines Freedman’s inequality across time steps and deviation cases through a union bound.The proof applies the inequality at selected variance levels and then combines the resulting events.
  • Auxiliary inequalities: The appendix also uses calculus inequalities relating differences of powers and logarithms to control weighted sums.These inequalities are applied to consecutive partial sums of stage-related quantities.
  • Weighted-sum lemmas: Additional lemmas bound expressions involving non-negative weights and stage-indexed quantities used in the main proof.Their proofs reduce the claims to inequalities for adjacent cumulative sums.

B.1 Proof of Proposition 4

The proof establishes the proposition by induction over episodes, handling the update and non-update cases for each state-action-stage triple. Concentration inequalities and a union bound then yield the stated high-probability conclusion.

  • Inductive argument: Induction over the episode index establishes the proposition for every state, action, and stage.The base case is k = 1, followed by the inductive step for k ≥ 2.
  • Case analysis: The inductive step separates the cases where Q_h(s,a) is updated and where it is not updated.The proof explicitly identifies two non-trivial cases associated with these alternatives.
  • Concentration bounds: Hoeffding’s and Azuma’s inequalities control the stochastic terms, while Cauchy–Schwarz handles a remaining term.The proof combines these inequalities with bounds involving transition values and conditional variances.
  • Conclusion: Combining the case bounds and applying a union bound over all time steps completes the proposition.The argument collects the associated probability bounds before concluding.

B.2 Proof of Lemma 5

The proof bounds the weighted error terms arising in Lemma 5 by conditioning on successful concentration events and controlling the resulting weight sums. Induction over the stage index then gives the claimed bound.

  • Sum bounds: Hoeffding’s inequality, rearrangement, and Cauchy–Schwarz control the component sums in the decomposition.The proof also uses monotonicity of the sequence 1{e_j} and bounds weighted stage contributions.
  • Weight control: For nonnegative weight sequences, the proof relates the maximum and total weight norms to sums over stages and episodes.The sequence norms are introduced explicitly through ||w||∞ and ||w||1.
  • Inductive conclusion: Induction on h combines the intermediate estimates into the final bound for the lemma.The induction uses the base case h = H and produces terms involving SAH and the weight norms.

B.3 Proof of Lemma 7

The proof of Lemma 7 combines concentration estimates for stage-wise quantities with bounds on variance and visit-dependent terms. Several auxiliary lemmas are assembled under a high-probability event to obtain the result.

  • Setup: The analysis is conditioned on successful events from Proposition 4 and Lemma 5 and uses auxiliary variables indexed by episodes and stages.The conditioning event is stated explicitly before the subsequent bounds are derived.
  • Variance control: A total-variance bound is established and combined with separate bounds for the four terms in the decomposition.Lemma 19 provides the variance control, while the proof separately analyzes the terms preceding it.
  • Concentration: Azuma’s inequality and union bounds control martingale terms across time steps and stages.The proof repeatedly invokes Azuma’s inequality, including a union bound over all time steps.
  • Visit decomposition: The proof bounds contributions from the final stages using their O(1/H) fraction of total visits.This stage-length observation is used alongside Cauchy–Schwarz in the second-term estimate.
  • Conclusion: Lemmas 11, 18, and 19 are combined with the preceding estimates to complete the proof of Lemma 7.The final step cites these lemmas together with equations (67), (79), and (81).

B.3.5 Putting Everything Together ?

The final section combines the preceding lemmas and parameter choices to obtain the overall high-probability bound. The displayed conclusion includes logarithmic and polynomial terms in the problem parameters.

  • Final combination: Combining Lemmas 14–17 with the preceding bound yields the final result with probability at least 1 − O(H^2T^4p(q)).The proof explicitly identifies this combination as the concluding step.
  • Bound structure: The final expression contains terms involving H^2SN0, H^4, and log(T).The displayed intermediate bounds retain these parameter-dependent contributions.

C.1 Local Switching Cost Analysis

UCB-ADVANTAGE bounds local switching through staged policy updates and extends the single-agent procedure to concurrent reinforcement learning. In the concurrent setting, parallel trajectories are processed as consecutive single-agent episodes, yielding an ϵ-optimal policy with improved episode complexity.

  • Local Switching Cost Analysis: UCB-ADVANTAGE’s local switching cost is analyzed through staged policy changes at each state, action, and time step.The analysis bounds the number of stages using a logarithmic argument based on the growth of the stage thresholds.
  • Local Switching Cost Analysis: The algorithm’s total local switching cost is bounded by a logarithmic expression in the number of episodes and state-action-time configurations.The supplied derivation concludes the bound using concavity of the logarithm.
  • Concurrent Reinforcement Learning: In concurrent reinforcement learning, M parallel agents independently complete episodes and exchange experience only at the end of each round.The goal is to obtain an ϵ-optimal policy using as few concurrent rounds, or concurrent episodes, as possible.
  • Concurrent Reinforcement Learning: Concurrent UCB-ADVANTAGE simulates the single-agent algorithm by treating the M episodes in each round as consecutive episodes without policy changes.Collected trajectories are fed to the single-agent procedure; when an update is triggered, the Q-function is updated and remaining trajectories are discarded.
  • Concurrent Reinforcement Learning: ˜O(H^2SA + H^3SA/(ϵ^2M)) concurrent episodes suffice to compute an ϵ-optimal policy with M parallel machines.The guarantee follows by selecting a random episode policy after the incurred regret over the exploration episodes is at most K_ϵϵ.

C.3 Lower Bound of the Sample Complexity

The paper establishes a sample-complexity lower bound for learning ϵ-optimal policies in episodic MDPs. Its hard-instance argument shows that some algorithms require on the order of SAH^3/ϵ^2 episodes, matching the stated upper bound up to logarithmic factors.

  • Lower-Bound Statement: Ω(SAH^3/ϵ^2) episodes are necessary in the worst case before policies become ϵ-optimal with probability at least 1/2.The theorem states that an episodic MDP exists with at least this many episodes whose policies remain more than ϵ below optimal.
  • Hard Instance: The lower-bound construction connects H two-state JAO MDPs with different optimal actions across layers.Each component hides the optimal action through a small transition-probability difference, and δ is chosen proportional to 1/H to keep the episodic MDP well mixed.
  • Hard Instance: If the agent cannot identify optimal actions in sufficiently many layers, it incurs Ω(H) mistakes across those layers.The construction then converts these mistakes into per-episode regret and, by rescaling ϵ, into the episode lower bound.
Loading 2004.10019v2…