# Large Scale Markov Decision Processes with Changing Rewards

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2019.

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

- [Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chains](https://mlsanity.com/paper/2201.12224/) (2022)
- [Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes](https://mlsanity.com/paper/2304.00232/) (2023)
- [Online Resource Allocation in Episodic Markov Decision Processes](https://mlsanity.com/paper/2305.10744/) (2023)
- [Scalable and Independent Learning of Nash Equilibrium Policies in n-Player Stochastic Games with Unknown Independent Chains](https://mlsanity.com/paper/2312.01587/) (2023)
- [Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPs](https://mlsanity.com/paper/2606.29092/) (2026)
- [Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics](https://mlsanity.com/paper/2608.18672/) (2026)
- [Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains](https://mlsanity.com/paper/2610.01181/) (2026)

## Abstract (arXiv)

We consider Markov Decision Processes (MDPs) where the rewards are unknown and may change in an adversarial manner. We provide an algorithm that achieves state-of-the-art regret bound of O( √τ (ln|S|+ln|A|)Tln(T)), where S is the state space, A is the action space, τ is the mixing time of the MDP, and T is the number of periods. The algorithm's computational complexity is polynomial in |S| and |A| per period. We then consider a setting often encountered in practice, where the state space of the MDP is too large to allow for exact solutions. By approximating the state-action occupancy measures with a linear architecture of dimension dll|S|, we propose a modified algorithm with computational complexity polynomial in d. We also prove a regret bound for this modified algorithm, which to the best of our knowledge this is the first tildeO(√T) regret bound for large scale MDPs with changing rewards.