# Information Capacity Regret Bounds for Bandits with Mediator Feedback

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 48 references that are in the map.
- First posted on arXiv 15 Feb 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [First-order regret bounds for combinatorial semi-bandits](https://mlsanity.com/paper/1502.06354/) (2015)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [Efficient Contextual Bandits with Continuous Actions](https://mlsanity.com/paper/2006.06040/) (2020)
- [Deciding What to Learn: A Rate-Distortion Approach](https://mlsanity.com/paper/2101.06197/) (2021)
- [Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces](https://mlsanity.com/paper/2207.05849/) (2022)
- [Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits](https://mlsanity.com/paper/1802.03386/) (2018)
- [Tight Bounds for Bandit Combinatorial Optimization](https://mlsanity.com/paper/1702.07539/) (2017)
- [Contextual Bandits with Stochastic Experts](https://mlsanity.com/paper/1802.08737/) (2018)
- [Policy Optimization as Online Learning with Mediator Feedback](https://mlsanity.com/paper/2012.08225/) (2020)
- [Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice](https://mlsanity.com/paper/2303.08102/) (2023)
- [Best Arm Identification in Bandits with Limited Precision Sampling](https://mlsanity.com/paper/2305.06082/) (2023)
- [Pure Exploration under Mediators' Feedback](https://mlsanity.com/paper/2308.15552/) (2023)

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

- [Improved Regret Bounds for Bandits with Expert Advice](https://mlsanity.com/paper/2406.16802/) (2024)
- [Generator-Mediated Bandits: Thompson Sampling for GenAI-Powered Adaptive Interventions](https://mlsanity.com/paper/2505.16311/) (2025)
- [Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring](https://mlsanity.com/paper/2510.19158/) (2025)
- [Pooling and Drift in Delayed Bandits](https://mlsanity.com/paper/2609.01761/) (2026)

## Abstract (arXiv)

This work addresses the mediator feedback problem, a bandit game where the decision set consists of a number of policies, each associated with a probability distribution over a common space of outcomes. Upon choosing a policy, the learner observes an outcome sampled from its distribution and incurs the loss assigned to this outcome in the present round. We introduce the policy set capacity as an information-theoretic measure for the complexity of the policy set. Adopting the classical EXP4 algorithm, we provide new regret bounds depending on the policy set capacity in both the adversarial and the stochastic settings. For a selection of policy set families, we prove nearly-matching lower bounds, scaling similarly with the capacity. We also consider the case when the policies' distributions can vary between rounds, thus addressing the related bandits with expert advice problem, which we improve upon its prior results. Additionally, we prove a lower bound showing that exploiting the similarity between the policies is not possible in general under linear bandit feedback. Finally, for a full-information variant, we provide a regret bound scaling with the information radius of the policy set.