# Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 43 references that are in the map.
- First posted on arXiv 25 May 2022.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Near-optimal Regret Bounds for Stochastic Shortest Path](https://mlsanity.com/paper/2002.09869/) (2020)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [No-Regret Exploration in Goal-Oriented Reinforcement Learning](https://mlsanity.com/paper/1912.03517/) (2019)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Dynamic Regret of Policy Optimization in Non-stationary Environments](https://mlsanity.com/paper/2007.00148/) (2020)
- [Variational Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1905.05857/) (2019)
- [A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/2007.05078/) (2020)
- [A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions](https://mlsanity.com/paper/1805.10066/) (2018)
- [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021)
- [Stochastic Shortest Path with Adversarially Changing Costs](https://mlsanity.com/paper/2006.11561/) (2020)
- [Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case](https://mlsanity.com/paper/2102.05284/) (2021)
- [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022)
- [Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition](https://mlsanity.com/paper/2012.04053/) (2020)
- [Efficient Learning in Non-Stationary Linear Markov Decision Processes](https://mlsanity.com/paper/2010.12870/) (2020)
- [Algorithms for Non-Stationary Generalized Linear Bandits](https://mlsanity.com/paper/2003.10113/) (2020)
- [Nonstationary Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2010.04244/) (2020)
- [Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path](https://mlsanity.com/paper/2106.08377/) (2021)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [Refined Lower Bounds for Adversarial Bandits](https://mlsanity.com/paper/1605.07416/) (2016)
- [Combinatorial Semi-Bandit in the Non-Stationary Environment](https://mlsanity.com/paper/2002.03580/) (2020)
- [Online Learning for Stochastic Shortest Path Model via Posterior Sampling](https://mlsanity.com/paper/2106.05335/) (2021)
- [Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation](https://mlsanity.com/paper/2105.01593/) (2021)
- [Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP](https://mlsanity.com/paper/2112.09859/) (2021)

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

- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Multi-granularity Knowledge Transfer for Continual Reinforcement Learning](https://mlsanity.com/paper/2401.15098/) (2024)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [A Unified Algorithm for Stochastic Path Problems](https://mlsanity.com/paper/2210.09255/) (2022)
- [Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses](https://mlsanity.com/paper/2602.07418/) (2026)
- [Layered State Discovery for Incremental Autonomous Exploration](https://mlsanity.com/paper/2302.03789/) (2023)

## Abstract (arXiv)

We initiate the study of dynamic regret minimization for goal-oriented reinforcement learning modeled by a non-stationary stochastic shortest path problem with changing cost and transition functions. We start by establishing a lower bound Omega((Bstar SATstar(Deltac + Bstar2DeltaP))1/3K2/3), where Bstar is the maximum expected cost of the optimal policy of any episode starting from any state, Tstar is the maximum hitting time of the optimal policy of any episode starting from the initial state, SA is the number of state-action pairs, Deltac and DeltaP are the amount of changes of the cost and transition functions respectively, and K is the number of episodes. The different roles of Deltac and DeltaP in this lower bound inspire us to design algorithms that estimate costs and transitions separately. Specifically, assuming the knowledge of Deltac and DeltaP, we develop a simple but sub-optimal algorithm and another more involved minimax optimal algorithm (up to logarithmic terms). These algorithms combine the ideas of finite-horizon approximation [Chen et al., 2022a], special Bernstein-style bonuses of the MVP algorithm [Zhang et al., 2020], adaptive confidence widening [Wei and Luo, 2021], as well as some new techniques such as properly penalizing long-horizon policies. Finally, when Deltac and DeltaP are unknown, we develop a variant of the MASTER algorithm [Wei and Luo, 2021] and integrate the aforementioned ideas into it to achieve widetildeO(minBstar S√ALK, (Bstar2S2ATstar(Deltac+BstarDeltaP))1/3K2/3) regret, where L is the unknown number of changes of the environment.