Efficient Restarts in Non-Stationary Model-Free Reinforcement Learning

AI summary

Overview

• Research area: Reinforcement learning (RL), specifically model-free RL in non-stationary environments where reward functions and transition dynamics change over time.
• Technical level: Intermediate. The paper assumes familiarity with episodic Markov decision processes (MDPs), Q-learning, regret, and exploration-exploitation trade-offs, but its core ideas are explained concretely with algorithms and experiments.
• Scope: The paper proposes three modifications to the restart mechanism of the model-free non-stationary RL algorithm RestartQ-UCB (Mao et al., 2022) and evaluates them in two non-stationary environments.

What This Paper Is About

RestartQ-UCB is a model-free algorithm for non-stationary episodic MDPs that occasionally "restarts" by erasing everything it has learned about the environment. The authors argue this design wastes information: restarts discard all learned Q-values (complete forgetting) and happen on a fixed schedule regardless of whether the current policy is actually incompatible with the environment (scheduled restarts). The paper's goal is to design smarter restart schemes that keep useful information and trigger restarts only when needed.

Key Contributions

1. Identification of two specific inefficiencies in RestartQ-UCB's restart design, which the authors call (1) complete forgetting and (2) scheduled restarts.
2. Three new restart paradigms — partial restarts, adaptive restarts, and selective restarts — that modify RestartQ-UCB and RANDOMIZEDQ (Wang et al., 2025).
3. A new upper bound (Lemma 1) on how much an optimal Q-value can change between two episodes, expressed in terms of the variation budgets Δ_r and Δ_p, proved by backwards induction on h.
4. A new pseudorandom non-stationary environment called RandomMDP, plus an empirical evaluation on Bidirectional Diabolical Combination Locks (BDCL) (Agarwal et al., 2020).

Main Findings

• Large regret reductions: The abstract reports a 74% and 91% decrease in dynamic regret in RandomMDP and BDCL, respectively, with an overall figure of up to 91% relative to RestartQ-UCB.
• Adaptive + partial restarts in BDCL: In abrupt BDCL, combining adaptive and partial restarts decreased RestartQ-UCB's dynamic regret by 45%; in RandomMDP the decrease was 74%.
• Selective restarts in abrupt BDCL: SelectiveRestarts + RANDOMIZEDQ achieved 91% less dynamic regret than RestartQ-UCB, and showed near-zero dynamic regret in abrupt BDCL at episode 7,500.
• RestartQ-UCB restarts too often: The authors observe that its large reward gap stems from restarting very frequently, usually at times when not restarting would still allow the maximum per-episode reward to be gained; adaptive restarts trigger far more sparingly.
• Partial restarts help most with sparse rewards: The authors expect (and illustrate in Figure 1 at episode 1001) that partial restarts help most in environments like BDCL, where learned Q-values can sit far below their theoretical maximums.
• Selective restarts fit RANDOMIZEDQ better than RestartQ-UCB: Because selective restarts only change a subset of Q-table entries, they work best on a base algorithm that converges quickly in stationary settings; the authors report this is the case for RANDOMIZEDQ.
• Practical hyperparameter finding: Although the theory requires small δ, the authors report that δ = 2 is the optimal setting empirically, setting ι = log(2/δ) to zero on line 8 of Algorithm 1 and thereby breaking the proofs in Mao et al. (2022).
• Overhead is small: Partial restarts have a negligible effect on time and space complexity; adaptive restarts need at worst O(T) space; selective restarts add roughly O(B) time per timestep, giving total time ≈ O(MH(C_π + B)) and auxiliary space ≈ O(S(HA + H + A) + B).

Methodology in Plain English

• Partial restarts address complete forgetting. Instead of resetting every Q-value to the theoretical maximum H − h + 1 at each restart, the algorithm takes the Q-value learned at the end of the epoch and adds the maximum possible change in the optimal Q-value, given the environment's variation budgets Δ_r and Δ_p. Lemma 1 shows this difference is bounded by Δ_r + ½ Δ_p times a term involving the Q-values of later timesteps. This requires two assumptions: that Q-values are optimistic (at or above optimal) right after a restart, and that a learned Q-value never falls below the lowest optimal Q-value during an epoch.
• Adaptive restarts address scheduled restarts. The agent tracks reward over a sliding window whose length W is determined by counting Q-table updates: if H² "true-updates" (where the optimal action changes) happen before H² "non-updates," learning is still ongoing and counters reset; otherwise learning is considered done and W is set to the elapsed episode count. It then compares the reward expected from not restarting, r_C · (T − t)/(HW), against the reward expected from restarting, r_L + r_B · ((T − t)/(HW) − 1), and restarts when the latter is larger.
• Selective restarts combine both ideas but update only a subset of Q-table entries. When the Lemma 1 bound β_h(s,a) exceeds the difference between the current step-wise Bellman update U_h^k(s,a) and the value U_h^{k_0}(s,a) from the last visit, the algorithm traces the trajectory and increments Q-values by an amount scaled by the sign of that difference, a softmax-based coefficient γ, and 1/(H − h′).
• Experiments: RandomMDP was tested with A = 5, S = 5, H = 5, T = 50,000; gradual and abrupt BDCL with A = 5, H = 5, T = 100,000 and fail probability 0.02, with abrupt changes every 1,001 episodes. Each trial was iterated 5 times. Baselines were RestartQ-UCB, a random policy, and the optimal policy. Following Mao et al. (2022), b_Δ was set to zero in the update rule. SelectiveRANDOMIZEDQ used 20 ensembles, inflation coefficient κ = 1, and n_0 = 1/4 prior transitions.

Why This Matters

• Research impact: The work attacks the gap between theory and practice in non-stationary RL, showing that a theoretically robust algorithm with an asymptotic guarantee can be made substantially more efficient through simple, outer "restart wrapper" modifications.
• Real-world applications (as framed in the paper's introduction):
  • Crop management, where growing conditions and yields change over time.
  • Inventory control, where demand and supply dynamics shift.
  • Board games and other interactive decision problems.
• Industry relevance: Because partial, adaptive, and selective restarts are described as wrappers that only modify the outside of an existing algorithm, the authors suggest they could be attached to other stationary RL algorithms — a cheap way to make deployed RL systems adapt to drifting environments without redesigning the base learner.

Future Directions

• Stronger theory for adaptive restarts: The current mechanism is heuristic and would not detect a change that does not decrease the agent's reward rate; the authors suggest a more theoretical design, possibly combining spaced-out scheduled restarts with adaptive ones.
• Provable selective restarts: The update amount in Equation 3 is heuristic and lacks a proof-based foundation. The authors also note that SelectiveRANDOMIZEDQ begins accumulating dynamic regret after some thousands of episodes, so the update trigger condition needs revisiting.
• Estimating variation budgets: Partial restarts assume knowledge of Δ_p and Δ_r, which is a strong assumption; alternatives are repeated sampling (likely poor theoretically) or using deliberately inflated budget values, which would bring behavior closer to full restarts.
• Broader evaluation and asymptotic analysis: Testing in more than the two settings used here, deriving asymptotic performance for these approaches, and applying the restart wrappers to other stationary algorithms.

Target Audience

Researchers and graduate students working on reinforcement learning theory and non-stationary MDPs; practitioners who want to adapt an existing model-free RL algorithm to changing environments with minimal changes to the base learner; and readers interested in the gap between asymptotic regret guarantees and empirical performance.

Authors’ abstract

In this work, we propose three efficient restart paradigms for model-free non-stationary reinforcement learning (RL). We identify two core issues with the restart design of Mao et al. (2022)'s RestartQ-UCB algorithm: (1) complete forgetting, where all the information learned about an environment is lost after a restart, and (2) scheduled restarts, in which restarts occur only at predefined timings, regardless of the incompatibility of the policy with the current environment dynamics. We introduce three approaches, which we call partial, adaptive, and selective restarts to modify the algorithms RestartQ-UCB and RANDOMIZEDQ (Wang et al., 2025). We find near-optimal empirical performance in multiple different environments, decreasing dynamic regret by up to $91$% relative to RestartQ-UCB.