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

2024/10/21 by Raghav Bongole, Amaury Gouverneur, Bongole, Raghav +7 · 1 citation
Computer Science · #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Neural Networks and Applications #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2410.16013

openalex publication_date 2024/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• "X of Information'' Continuum: A Survey on AI-Driven Multi-dimensional Metrics for Next-Generation Networked Systems

Related

• An Information-Theoretic Analysis of Bayesian Reinforcement Learning
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes
• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• Posterior sampling for reinforcement learning: worst-case regret bounds
• Regret Analysis in Deterministic Reinforcement Learning