PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach

Chen-Yu Wei, Haipeng Luo

arXiv:2102.05406v3cs.LGcs.AIstat.ML

TL;DR

Non-stationary reinforcement learning calls for dynamic-regret guarantees, yet existing approaches often require prior knowledge of how much or how often the environment changes. MASTER reduces a near-stationary algorithm to one for non-stationary settings, achieving both principal dynamic-regret bounds without prior knowledge of the degree of non-stationarity.

  • Problem

    Dynamic regret is more meaningful than static regret in non-stationary environments, but existing approaches often require prior knowledge of the amount or number of changes.

    Source: §1 · p. 1

  • Method

    MASTER is a black-box reduction that converts an algorithm with near-optimal performance in a near-stationary environment into one for non-stationary environments, without prior knowledge of the degree of non-stationarity.

    Source: §1 · pp. 1–2

  • Results

    MASTER achieves both principal dynamic-regret bounds simultaneously without prior knowledge of L or Δ.

    Source: §5 · p. 11

  • Takeaways & Limitations

    The reduction recovers recent (contextual) bandit results and improves prior results for linear bandits and episodic and infinite-horizon MDPs in various ways.

    Source: §1 · p. 1

    Whether the optimal bound is achievable when L, Δ, and Dmax are all unknown remains an open question.

    Source: §4.2 · p. 11

Abstract

from arXiv · show

We propose a black-box reduction that turns a certain reinforcement learning algorithm with optimal regret in a (near-)stationary environment into another algorithm with optimal dynamic regret in a non-stationary environment, importantly without any prior knowledge on the degree of non-stationarity. By plugging different algorithms into our black-box, we provide a list of examples showing that our approach not only recovers recent results for (contextual) multi-armed bandits achieved by very specialized algorithms, but also significantly improves the state of the art for (generalized) linear bandits, episodic MDPs, and infinite-horizon MDPs in various ways. Specifically, in most cases our algorithm achieves the optimal dynamic regret $\widetilde{\mathcal{O}}(\min\{\sqrt{LT}, \Delta^{1/3}T^{2/3}\})$ where $T$ is the number of rounds and $L$ and $\Delta$ are the number and amount of changes of the world respectively, while previous works only obtain suboptimal bounds and/or require the knowledge of $L$ and $\Delta$.

1 Introduction

In non-stationary reinforcement learning, dynamic regret is more meaningful than static regret, but existing approaches often require prior knowledge of how the world changes. MASTER is a black-box reduction that applies across reinforcement-learning settings and achieves dynamic-regret guarantees without that prior knowledge.

1 Introduction

  • Prior non-stationary RL methods commonly require knowledge of the amount or number of changes, while the BoRL framework adds overhead and has suboptimal regret.Specialized bandit methods without such prior knowledge are described as difficult to extend to standard reinforcement-learning algorithms.Source: §1 · p. 1
  • MASTER’s examples recover optimal (contextual) bandit results and improve prior bounds for linear and generalized linear bandits and episodic MDPs; infinite-horizon results have additional conditions.For infinite-horizon MDPs, the optimal regret is achieved when the maximum MDP diameter is known or when L and Δ are known.Source: §1 · p. 2
  • For infinite-horizon MDPs, MASTER attains the optimal regret when the maximum diameter is known or when L and Δ are known.If none of these quantities is known, the BoRL technique incurs extra T^3/4 regret, which is suboptimal but still improves on the best known results.Source: §1 · p. 2
  • Earlier linear-bandit methods claiming optimal bounds with known Δ had technical flaws; after correction, their bounds weakened, while an adversarial-algorithm approach achieved a tight bound when Δ was known.MASTER instead uses stochastic linear-bandit algorithms and avoids requiring knowledge of Δ.Source: §1 · p. 3
  • MASTER schedules base-algorithm instances with different durations and follows the currently shortest one to detect distribution changes at multiple scales.The reduction converts an algorithm with near-optimal stationary-environment performance and mild additional requirements into one with dynamic-regret guarantees; UCB-based algorithms can be plugged in.Source: §1 · pp. 1–3

2 Problem Setting, Main Results, and High-level Ideas

The section sets up dynamic regret for a general policy-based reinforcement-learning framework and specifies the guarantees required of a base algorithm. It presents MASTER’s regret guarantee and sketches how parallel instances help detect changes and trigger restarts.

2.1 Problem setting

  • The framework treats policies as actions with unknown, changing rewards and measures performance by dynamic regret against the sequence of optimal policies.Its non-stationarity measure bounds how much any policy’s expected reward can change between rounds.Source: §2.1 · p. 4
  • MASTER requires a base algorithm with an optimistic estimate and regret guarantee that remain useful when the environment is near-stationary.The near-stationary-only requirement is identified as key to obtaining the claimed regret bound; the paper notes that UCB-based algorithms satisfy the assumption in its examples.Source: §2.1 · pp. 4–5

2.2 Main results

  • MASTER guarantees high-probability dynamic regret without knowing L or Δ, and applying the theorem yields the stated optimal min{Reg⋆, Δ} bounds for the listed examples.The listed examples recover the cited contextual-bandit bounds and improve results in other settings; infinite-horizon MDPs are handled separately.Source: §2.2 · pp. 5–6

2.3 High-level ideas

  • Multiple base-algorithm instances help detect a change when a newer instance outperforms the minimum optimistic estimate, prompting a restart.The approach uses a randomized multi-scale schedule to decide when instances start and how long they run.Source: §2.3 · pp. 6–7

3 Algorithm

MALG schedules instances of a base algorithm at multiple time scales, while MASTER adds stationarity tests and restarts. The resulting scheme retains interval-level regret guarantees and uses them to detect non-stationarity.

3.1 MALG: Running the Base Algorithm with Multiple Scales

  • MALG schedules base-algorithm instances of different lengths within each block and follows the shortest instance covering the current round.The instances are randomized across sub-intervals; inactive instances pause and can later resume.Source: §3.1 · p. 7
  • For an instance whose interval remains near-stationary, MALG retains a regret guarantee close to running ALG alone on that interval.The multi-scale construction also bounds how many instances start within the interval, up to logarithmic factors.Source: §3.1 · pp. 8–9

3.2 MASTER: Equipping MALG with Stationarity Tests

  • MASTER runs MALG in doubling-length blocks and restarts from scratch when either stationarity test fails.One test detects an instance outperforming the block’s minimum optimistic estimate; the other tests whether accumulated regret exceeds its bound.Source: §3.2 · p. 9
  • A high-probability lemma bounds MASTER’s dynamic regret on each block, including blocks ended early by a restart.The analysis relates the block bound to partitions whose sub-intervals meet the stated non-stationarity condition.Source: §3.2 · p. 9

4 Extension to Reinforcement Learning in Infinite-horizon Communicating MDPs

The infinite-horizon extension treats each state transition as a round, then combines an appropriate base algorithm with MASTER’s multi-scale scheduling and detection. Its UCRL-based construction adapts confidence widening and handles unknown parameters with stated bounds that depend on what is known.

4 Extension to Reinforcement Learning in Infinite-horizon Communicating MDPs

  • Each state transition is one round in infinite-horizon RL, with no episode reset; MASTER can be applied when a suitable base algorithm is available.The reward feedback is the reward for the single step rather than a noisy observation of the policy’s round reward.Source: §4 · p. 10

4.1 UCRL with Adaptive Confidence Widening

  • UCRL-ACW widens confidence sets adaptively and signals a restart when cumulative widening exceeds a threshold.The widening grows by doubling as non-stationarity increases; the threshold is intended to flag a highly non-stationary environment.Source: §4.1 · p. 10

4.2 Multi-scale UCRL-ACW and Its Combination with MASTER

  • MUCRL combines multi-scale scheduling with UCRL-ACW, while MASTER-UCRL also restarts when an active UCRL-ACW instance signals a restart.The paper provides a fixed-D guarantee for MASTER-UCRL.Source: §4.2 · pp. 10–11
  • When Dmax is known, MASTER-UCRL achieves a dynamic-regret bound depending on the base-regret bound and Δ.The paper gives the dependence on other parameters in Theorem 28.Source: §4.2 · p. 11
  • When Dmax is unknown, the stated bound requires knowledge of L or Δ, and a doubling strategy adjusts the guess D.The paper compares this result with prior bounds when L and Δ are known.Source: §4.2 · p. 11
  • When L, Δ, and Dmax are all unknown, applying BoRL gives a suboptimal bound, and achieving the optimal bound remains open.The authors leave this parameter-free optimal-regret question for future work.Source: §4.2 · p. 11

5 Conclusion and Future Directions

The conclusion presents a black-box reduction for dynamic regret without prior knowledge of non-stationarity, achieving both previously unavailable bounds simultaneously. It also identifies data-dependent algorithms, adversarial contexts, and convex bandits as open directions or scope boundaries.

5 Conclusion and Future Directions

  • The black-box approach converts a near-optimal stationary-regret algorithm into one with near-optimal dynamic regret in non-stationary environments.The conclusion describes the approach as general.Source: §5 · p. 11
  • The algorithm achieves both the Δ-based and L-based bounds simultaneously without prior knowledge.Previously, the Δ-based bound required knowing Δ, while no algorithm achieved the L-based bound even when L was known.Source: §5 · p. 11
  • Data-dependent dynamic bounds without prior knowledge remain challenging because regret-bound monotonicity may fail and the restart probability is unclear.The paper notes that applying the approach to data-dependent algorithms would be interesting to investigate.Source: §5 · p. 11
  • For adversarial contexts, the current algorithm does not directly apply, and extending it to general contextual bandits without hidden-parameter confidence sets is unclear.The paper separately notes that the extension is straightforward for linear contextual bandits with adversarial contexts.Source: §5 · pp. 11–12
  • Near-optimal dynamic regret for general convex bandits remains open because the authors know of no near-optimal convex bandit algorithm satisfying Assumption 1.Source: §5 · p. 12

A Omitted Algorithms and Main Results in Section 4

The infinite-horizon MDP results give several UCRL-based algorithm variants with different parameter inputs, including one that requires none of L, Δ, or Dmax. The appendix also supplies supporting EVI facts and guarantees for UCRL-ACW.

A Omitted Algorithms and Main Results in Section 4

  • UCRL-ACW uses adaptive confidence widening and early termination to signal restarts, while MUCRL runs it as its base algorithm.The algorithm description also terminates MUCRL when its active instance signals restart.Source: A Omitted Algorithms and Main Results… · p. 16
  • One infinite-horizon MDP variant achieves a bound without knowing L, Δ, or Dmax; other variants take Dmax or L/Δ as inputs.The theorem passage also states variants that take Dmax or L or Δ as input, but the supplied text does not expose their bound expressions.Source: A Omitted Algorithms and Main Results… · p. 17

A.1 Auxiliary Lemmas related to Extended Value Iteration and Bellman Equation

  • The EVI lemmas bound the span of its bias function by 2D when the confidence sets contain an MDP of diameter at most D, and establish an optimistic average-reward estimate.The average-reward statement is conditional on the displayed Bellman-style conditions for the bounded estimates.Source: §A.1 · p. 18

A.2 Guarantees of the UCRL-ACW Algorithm (when running alone with an input D)

  • The UCRL-ACW analysis tracks reward and transition drift, confidence-set coverage, and state reassignments before the algorithm terminates.The supplied passages indicate that the regret analysis includes a state-reassignment term and uses Azuma’s inequality.Source: §A.2 · pp. 18–19

B Analysis for the Multi-scale Algorithms

The multi-scale analysis controls the base algorithm’s behavior over active intervals and accounts for the additional cost of state reassignments. Its guarantees apply before MUCRL terminates.

B Analysis for the Multi-scale Algorithms

  • Within an active interval, the multi-scale analysis applies the base algorithm’s guarantee when the drift is bounded by the decreasing function ρ.The proof relates drift over the interval to the active run length of the relevant instance.Source: B Analysis for the Multi-scale… · pp. 19–20
  • The MUCRL guarantee is stated for each active instance and time before termination, with the bound parameterized by interval length and drift.The passage defines t′ as elapsed time since the instance started.Source: B Analysis for the Multi-scale… · p. 21
  • MUCRL’s bound accounts for state reassignments by charging their count to newly started lower-order instances.For each order m, the total reassignments among its instances are bounded using the number of new instances of order at most m−1.Source: B Analysis for the Multi-scale… · p. 21

C Single-block Regret Analysis I

The single-block analysis partitions a block into intervals with controlled drift and uses tests and restarts to detect when the learner’s estimate lags the optimal reward. It derives high-probability regret bounds for the standard and infinite-horizon RL cases.

C Single-block Regret Analysis I

  • The section states high-probability single-block regret bounds for both the standard setting and infinite-horizon MDPs.The block may end early if a stationarity test fails or MUCRL terminates.Source: C Single-block Regret Analysis I · p. 22
  • The block is partitioned into intervals where the distribution is close to stationary, independently of learner behavior.One described choice uses stationary intervals, while the analysis relates the number of intervals to cumulative drift.Source: C Single-block Regret Analysis I · p. 22
  • A sufficiently large gap between optimal reward and the learner’s estimate, sustained long enough, lets the learner detect the gap and restart.The analysis formalizes this intuition through τ_i(m) and ξ_i(m), with a complete order-m instance required to run within the interval.Source: C Single-block Regret Analysis I · p. 22

D Single-block Regret Analysis II (under a Special Form of C(·))

Under a specified form of the base regret function, the analysis combines single-block regret with bounds on the number of intervals. It obtains alternatives based on the number of changes or their total amount.

D Single-block Regret Analysis II (under a Special Form of C(·))

  • When C(t) = min{c1t^p + c2, c3t}, the block analysis bounds regret using either the number of changes or the amount of change.The section combines the single-block bound with an upper bound on the required number of intervals.Source: D Single-block Regret Analysis II… · pp. 25–26
  • The candidate interval count is bounded by the number of changes, and a second bound follows by greedily partitioning intervals according to their drift.The greedy partition keeps each interval’s drift within ρ of its length, while the next interval’s extended drift exceeds that threshold.Source: D Single-block Regret Analysis II… · p. 25
  • The analysis summarizes block dynamic regret after dropping a term whose contribution is vacuous in the regime where it exceeds the block-length scale.It notes that c1 2^np > 2n when c1 > 2^n(1−p).Source: D Single-block Regret Analysis II… · p. 26

E Single-epoch Regret Analysis

This section bounds dynamic regret within a single epoch by aggregating bounds over its blocks. The analysis applies when the single-block regret has the stated form, including the standard and infinite-horizon MDP settings.

E Single-epoch Regret Analysis

  • An epoch runs from the first step after a restart, or round 1, through the first time a new restart is triggered.Source: E Single-epoch Regret Analysis · p. 27
  • The single-epoch analysis applies in both the standard setting and the infinite-horizon MDP setting when the single-block regret has the specified form.Source: E Single-epoch Regret Analysis · p. 27
  • The single-epoch dynamic regret is bounded by eO(Reg_L(E)) after aggregating blockwise bounds and absorbing the logarithmic block count.The epoch’s last block index n satisfies |E| = Θ(2^n), so n = O(log T).Source: E Single-epoch Regret Analysis · p. 27

F Proof of Theorem 2

The proof of Theorem 2 controls when epochs end, bounds their number, and combines their regret contributions. It also identifies dominant terms for different values of p.

F Proof of Theorem 2

  • If cumulative drift within an epoch stays at most ρ(t − t0 + 1), no restart is triggered by time t with high probability.Source: F Proof of Theorem 2 · p. 28
  • For each order-m base-algorithm instance, Test 1 and Test 2 do not fail with high probability under the analyzed conditions.Source: F Proof of Theorem 2 · p. 28
  • The number of epochs is at most L with high probability; the proof also uses C(t) = min{c1t^p + c2, t} when aggregating regret across epochs.Source: F Proof of Theorem 2 · p. 28
  • The proof collects only non-dominated terms and treats p = 1/2 separately from p > 1/2.Source: F Proof of Theorem 2 · p. 29

G Main Results for Infinite-horizon MDP

The infinite-horizon MDP analysis bounds restart behavior and regret across epochs. For unknown Dmax with known L, the doubling-trick strategy has a dynamic-regret bound scaling with the combined reward and transition variation.

G Main Results for Infinite-horizon MDP

H Bandit-over-Reinforcement-Learning Approach

This section presents a bandit-over-reinforcement-learning scheme that aggregates MASTER-UCRL variants using different non-stationarity guesses, and verifies the required assumption for several bandit and MDP algorithms. It also states that Eq. (32) is satisfied.

H Bandit-over-Reinforcement-Learning Approach

  • EXP3.P aggregates MASTER-UCRL sub-algorithms using different guesses for Dmax, and the resulting regret combines its comparison to a near-correct guess with that sub-algorithm’s interval regret.The candidate guesses span a logarithmic range, and each sub-algorithm restarts at interval boundaries.Source: H Bandit-over-Reinforcement-Learning… · p. 33

I Verifying Assumption 1 for Several Algorithms

  • The section establishes Assumption 1’ as sufficient for proving Eq. (1), with brief verifications that follow standard analyses and sometimes modify algorithms for framework alignment.The authors note that some proofs are sketches and refer readers to prior work for details.Source: I Verifying Assumption 1 for Several… · p. 34

I.1 UCB1 for Multi-armed Bandits

  • For multi-armed bandits, UCB1 [Auer et al., 2002a] satisfies Assumption 1’, and its verification does not need the cumulative-variation condition.The argument uses high-probability reward bounds and the algorithm’s arm-selection rule.Source: §I.1 · pp. 34–35

I.2 OFUL for Linear Bandits

  • For linear bandits with a fixed action set, OFUL [Abbasi-Yadkori et al., 2011] satisfies both required inequalities under the stated boundedness assumptions.The setup assumes action vectors and reward vectors have Euclidean norm at most 1.Source: §I.2 · pp. 35–36

I.3 GLM-UCB for Generalized Linear Bandits

  • For generalized linear bandits with a fixed action set, GLM-UCB satisfies the two required inequalities under the stated variation condition.The setting uses an increasing link function and bounded action and parameter vectors.Source: §I.3 · pp. 36–38

I.4 Q-UCB for Finite-horizon Tabular MDPs

  • For finite-horizon tabular MDPs with a fixed initial state, prior analysis shows Q-UCB [Jin et al., 2018] satisfies Assumption 1’.Policies are deterministic, and each policy’s value is its expected reward in an episode.Source: §I.4 · p. 38

I.5 LSVI-UCB for Finite-horizon Linear MDPs

  • For finite-horizon linear MDPs, LSVI-UCB [Jin et al., 2020b] satisfies both required inequalities when cumulative variation is bounded by the specified threshold.The verification uses optimism and standard LSVI-UCB analysis.Source: §I.5 · p. 39

I.6 ILOVETOCONBANDITS for Contextual Bandits

  • ILOVETOCONBANDITS [Agarwal et al., 2014] satisfies Assumption 1 even for large cumulative variation, and the reused analysis avoids an additional log T factor.The guarantee draws on lemmas from Chen et al. [2019].Source: §I.6 · p. 40
  • Eq. (32) is also satisfied.Source: §I.6 · p. 41

I.7 FALCON for Contextual Bandits

The section analyzes FALCON for realizable contextual bandits in the framework, reporting bounds of stationary-case order when the change condition holds. It also describes a per-round regression-oracle modification.

I.7 FALCON for Contextual Bandits

  • FALCON uses a function class containing the unknown reward function to define candidate policies, with the goal of competing against the optimal policy πφ⋆.The framework sets Π = {πφ : φ ∈ Φ} and defines ft(π) as the expected reward under the context distribution at time t.Source: §I.7 · p. 41
  • The modified algorithm calls the regression oracle once each round, rather than only when the time index doubles, then constructs an action distribution from the fitted function.Source: §I.7 · p. 41
  • Equation (47) bounds Reg[1,t](π) by 2d Reg[1,t](π) + O(ρ(t)) and d Reg[1,t](π) by 2Reg[1,t](π) + O(ρ(t)).Source: §I.7 · p. 43
  • Under ∆[1,t] = O(ρ(t)), the bounds obtained are of the same order as in the stationary case [Simchi-Levi and Xu, 2020].The comparison is explicitly conditioned on ∆[1,t] = O(ρ(t)).Source: §I.7 · p. 43
Loading 2102.05406v3…