kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Information-Theoretic Minimax Regret Upper Bounds for Reinforcement Learning Problems
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Information Science and Engineering.ORCID iD: 0000-0003-3906-8806
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Information Science and Engineering.ORCID iD: 0000-0003-2598-4459
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Information Science and Engineering.ORCID iD: 0000-0002-0036-9049
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Information Science and Engineering.ORCID iD: 0000-0002-7926-5081
2025 (English)In: 2025 IEEE Information Theory Workshop, ITW 2025, Institute of Electrical and Electronics Engineers Inc. , 2025Conference paper, Published paper (Refereed)
Abstract [en]

We study different classes of reinforcement learning problems using the minimax regret framework. We formalize a finite-horizon reinforcement learning problem setting that is suitable for the information-theoretic analysis of minimax regret which encompasses linear bandits, Markov decision processes, linear Markov decision processes, and other reinforcement learning problems. We derive a minimax theorem applicable to this setting that does not require any finiteness or deterministic policy constraints. Using this theorem, we show that any Bayesian regret bound can be used to bound the minimax regret within our framework. We then apply the minimax theorem to obtain an information-theoretic upper bound for the minimax regret, leveraging a general Bayesian regret bound. The derived minimax regret bound inherits key properties of the Bayesian regret bound, including its ability to isolate factors such as the information ratio, the mutual information between the learning target and the environment, and the Bayesian regret of the target policy. Finally, we demonstrate the applicability of our bounds in various settings, including linear bandits, episodic reinforcement learning, and linear Markov decision processes, recovering known results for the minimax regret.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc. , 2025.
Keywords [en]
information theory, minimax theorems, reinforcement learning
National Category
Computer Sciences Control Engineering Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:kth:diva-377365DOI: 10.1109/ITW62417.2025.11240440Scopus ID: 2-s2.0-105029045589OAI: oai:DiVA.org:kth-377365DiVA, id: diva2:2042055
Conference
2025 IEEE Information Theory Workshop, ITW 2025, Sydney, Australia, September 29 - October 3, 2025
Note

Part of ISBN 9798331531423

QC 20260226

Available from: 2026-02-26 Created: 2026-02-26 Last updated: 2026-02-26Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Bongole, RaghavGouverneur, AmauryOechtering, Tobias J.Skoglund, Mikael

Search in DiVA

By author/editor
Bongole, RaghavGouverneur, AmauryOechtering, Tobias J.Skoglund, Mikael
By organisation
Information Science and Engineering
Computer SciencesControl EngineeringProbability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 12 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf