# Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 38 references that are in the map.
- First posted on arXiv 15 Jun 2021.

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

- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Applications of Deep Reinforcement Learning in Communications and Networking: A Survey](https://mlsanity.com/paper/1810.07862/) (2018)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Multi-Agent Deep Reinforcement Learning for Dynamic Power Allocation in Wireless Networks](https://mlsanity.com/paper/1808.00490/) (2018)
- [Deep-Reinforcement Learning Multiple Access for Heterogeneous Wireless Networks](https://mlsanity.com/paper/1712.00162/) (2017)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Variational Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1905.05857/) (2019)
- [Online Regret Bounds for Undiscounted Continuous Reinforcement Learning](https://mlsanity.com/paper/1302.2550/) (2013)
- [A Reinforcement-Learning Approach to Proactive Caching in Wireless Networks](https://mlsanity.com/paper/1712.07084/) (2017)
- [Multi-Tenant Cross-Slice Resource Orchestration: A Deep Reinforcement Learning Approach](https://mlsanity.com/paper/1807.09350/) (2018)

## Abstract (arXiv)

Online reinforcement learning (RL) has been widely applied in information processing scenarios, which usually exhibit much uncertainty due to the intrinsic randomness of channels and service demands. In this paper, we consider an un-discounted RL in general Markov decision processes (MDPs) with both endogeneous and exogeneous uncertainty, where both the rewards and state transition probability are unknown to the RL agent and evolve with the time as long as their respective variations do not exceed certain dynamic budget (i.e., upper bound). We first develop a variation-aware Bernstein-based upper confidence reinforcement learning (VB-UCRL), which we allow to restart according to a schedule dependent on the variations. We successfully overcome the challenges due to the exogeneous uncertainty and establish a regret bound of saving at most √S or S^frac16T^frac112 compared with the latest results in the literature, where S denotes the state size of the MDP and T indicates the iteration index of learning steps.