Research map / Bandits and online learning / Online convex optimization and games

Optimal Dynamic Regret by Transformers for Non-Stationary Reinforcement Learning

NeurIPS 2025 · Bandits and online learning › Online convex optimization and games · approach: Online linear-quadratic control regret · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows theoretically that transformers trained by supervised in-context learning can approximate MASTER-style non-stationary RL algorithms (window scheduler plus restarts), achieving near-optimal dynamic regret for bandits, and validates with linear bandit experiments against LinUCB/TS and MASTER variants.

Problem

Whether transformers trained in an in-context learning setup can adapt to non-stationary reinforcement learning environments and achieve near-optimal dynamic regret.

Approach

Constructs a (non-continuous) transformer that approximates the MASTER algorithm's multi-scale window scheduler and restart/stationarity tests, shows that supervised pretraining on base-algorithm trajectories yields a policy whose regret matches the minimax dynamic regret rate up to an approximation and generalization error.

Key results

• Transformer (GPT-2, 16 layers, 16 heads) achieves cumulative regret comparable to or better than LinUCB, TS, and MASTER variants in low and high non-stationary linear bandits (b=0.018).
• Theory: with N >= C T^3 log T and epsilon <= T^{-3}, dynamic regret is O~(min{sqrt(JT), Delta^{1/3} T^{2/3} + sqrt(T)}), matching the optimal rate.
• For b=0.025 (outside training range), the transformer no longer outperforms the other models.

Measured effects reported in the paper

Surprising findings

• Transformer fails to outperform baselines when non-stationarity is higher (b=0.025), attributed to limited training coverage.

Limitations

• Experiments limited to linear bandit setting and comparisons with only two RL algorithms and their MASTER variants.
• Theory requires very large models and datasets (small approximation error, N >= T^3 log T), and uses a non-continuous transformer variant for proof simplicity.
• Transformer performance degrades under out-of-distribution non-stationarity levels.

Experimental setup

Datasets: synthetic linear bandit trajectories

Benchmarks: synthetic linear bandit (d=32, A=10), low and high non-stationarity

Metrics: cumulative regret suboptimality

Baselines: LinUCB Thompson Sampling MASTER+LinUCB MASTER+TS

Builds on: MASTER LinUCB Thompson Sampling Lin et al. 2024 offline-to-online generalization theory Transformers learn in-context RL (Lee et al.)

Closest papers by meaning

• Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretraining (ICLR 2024 · similarity 0.89)
• In-Context Reinforcement Learning From Suboptimal Historical Data (ICML 2025 · similarity 0.88)
• DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.88)
• Transformers Provably Implement In-Context Reinforcement Learning with Policy Improvement (NeurIPS 2026 · similarity 0.88)
• MetaCURL: Non-stationary Concave Utility Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
• Pausing Policy Learning in Non-stationary Reinforcement Learning (ICML 2024 · similarity 0.88)