# Optimal Dynamic Regret by Transformers for Non-Stationary Reinforcement Learning

arXiv: https://arxiv.org/abs/2508.16027 · HTML: https://mlsanity.com/paper/2508.16027/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 30 of its 47 references that are in the map.
- First posted on arXiv 22 Aug 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 30)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Multi-Game Decision Transformers](https://mlsanity.com/paper/2205.15241/) (2022)
- [In-context Reinforcement Learning with Algorithm Distillation](https://mlsanity.com/paper/2210.14215/) (2022)
- [Foundation Models for Decision Making: Problems, Methods, and Opportunities](https://mlsanity.com/paper/2303.04129/) (2023)
- [Few-shot Fine-tuning vs. In-context Learning: A Fair Comparison and Evaluation](https://mlsanity.com/paper/2305.16938/) (2023)
- [Q-Transformer: Scalable Offline Reinforcement Learning via Autoregressive Q-Functions](https://mlsanity.com/paper/2309.10150/) (2023)
- [In-Context Learning with Long-Context Models: An In-Depth Exploration](https://mlsanity.com/paper/2405.00200/) (2024)
- [Transformer for Graphs: An Overview from Architecture Perspective](https://mlsanity.com/paper/2202.08455/) (2022)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretraining](https://mlsanity.com/paper/2310.08566/) (2023)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [The Transient Nature of Emergent In-Context Learning in Transformers](https://mlsanity.com/paper/2311.08360/) (2023)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Transformers Implement Functional Gradient Descent to Learn Non-Linear Functions In Context](https://mlsanity.com/paper/2312.06528/) (2023)
- [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019)
- [Transformers are Universal In-context Learners](https://mlsanity.com/paper/2408.01367/) (2024)
- [A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/2007.05078/) (2020)
- [Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thought](https://mlsanity.com/paper/2502.21212/) (2025)
- [Randomized Exploration for Non-Stationary Stochastic Linear Bandits](https://mlsanity.com/paper/1912.05695/) (2019)
- [Probing the Decision Boundaries of In-context Learning in Large Language Models](https://mlsanity.com/paper/2406.11233/) (2024)
- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [Continuous-Time Multi-Armed Bandits with Controlled Restarts](https://mlsanity.com/paper/2007.00081/) (2020)

## Built on by (most cited first, 2 of 2)

- [In-Context Reinforcement Learning under Non-Stationarity: A Survey](https://mlsanity.com/paper/2607.11906/) (2026)
- [Provable Transformer Context Compression for In-Context Reinforcement Learning](https://mlsanity.com/paper/2610.20004/) (2026)

## Abstract (arXiv)

Transformers have demonstrated exceptional performance across a wide range of domains. While their ability to perform reinforcement learning in-context has been established both theoretically and empirically, their behavior in non-stationary environments remains less understood. In this study, we address this gap by showing that transformers can achieve nearly optimal dynamic regret bounds in non-stationary settings. We prove that transformers are capable of approximating strategies used to handle non-stationary environments and can learn the approximator in the in-context learning setup. Our experiments further show that transformers can match or even outperform existing expert algorithms in such environments.