# Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality

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

## Key facts

- Cited by 1 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 13 of its 24 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## 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, 13 of 13)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)
- [Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2012.14868/) (2020)
- [Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning](https://mlsanity.com/paper/2105.04180/) (2021)
- [Minimax-Bayes Reinforcement Learning](https://mlsanity.com/paper/2302.10831/) (2023)
- [Information-Theoretic Analysis of Minimax Excess Risk](https://mlsanity.com/paper/2202.07537/) (2022)
- [Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewards](https://mlsanity.com/paper/2304.13593/) (2023)
- [Lossless Transformations and Excess Risk Bounds in Statistical Inference](https://mlsanity.com/paper/2307.16735/) (2023)

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

- ["X of Information'' Continuum: A Survey on AI-Driven Multi-dimensional Metrics for Next-Generation Networked Systems](https://mlsanity.com/paper/2507.19657/) (2025)

## Abstract (arXiv)

We study agents acting in an unknown environment where the agent's goal is to find a robust policy. We consider robust policies as policies that achieve high cumulative rewards for all possible environments. To this end, we consider agents minimizing the maximum regret over different environment parameters, leading to the study of minimax regret. This research focuses on deriving information-theoretic bounds for minimax regret in Markov Decision Processes (MDPs) with a finite time horizon. Building on concepts from supervised learning, such as minimum excess risk (MER) and minimax excess risk, we use recent bounds on the Bayesian regret to derive minimax regret bounds. Specifically, we establish minimax theorems and use bounds on the Bayesian regret to perform minimax regret analysis using these minimax theorems. Our contributions include defining a suitable minimax regret in the context of MDPs, finding information-theoretic bounds for it, and applying these bounds in various scenarios.