Information Capacity Regret Bounds for Bandits with Mediator Feedback

Aug 2, 2026

Upload by Ezra

This work studies the mediator feedback problem in a multi-armed bandit setting, where each policy corresponds to a probability distribution over outcomes. After selecting a policy, the learner observes a sampled outcome and incurs the loss assigned to that outcome for the current round. The paper introduces policy set capacity as an information-theoretic measure of policy-set complexity, then derives new regret bounds under both adversarial and stochastic regimes using the classical EXP4 algorithm. It also proves nearly-matching lower bounds for selected policy families, extends to varying per-round policies (bandits with expert advice), and shows limitations for exploiting policy similarity in linear bandit feedback, plus a full-information bound via information radius.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages37

Reading Time1 h 33 min

Introduction

Multi-armed bandits and regret

Information leakage and structured feedback

Linear bandits and graph-feedback learning

Mediator feedback setting

Policies as outcome distributions

Loss maps and observations

POLITECNICO DI TORINO Repository ISTITUZIONALE Information Capacity Regret Bounds for Bandits with Mediator Feedback Original Information Capacity Regret Bounds for Bandits with Mediator Feedback / Eldowa, Khaled; Cesa-Bianchi, Nicolò; Maria Metelli, Alberto; Restelli, Marcello. -In: JOURNAL OF MACHINE LEARNING RESEARCH. -ISSN 1533-7928. - 25:(2024), pp. 1-36. Availability: This version is available at: 11583/2994771 since: 2024-11-25T18:59:03Z Publisher: Journal of Machine Learning Research Published DOI: Terms of use: This article is made available under terms and conditions as specified in the corresponding bibliographic description in the repository Publisher copyright (Article begins on next page) 17 February 2025 Information Capacity Regret Bounds for Bandits with Mediator Feedback Khaled Eldowa [khaled.eldowa@unimi.it](khaled.eldowa@unimi.it) Universit􀀒a degli Studi di Milano Milano, 20133, Italy Nicol􀀒o Cesa-Bianchi [nicolo.cesa-bianchi@unimi.it](nicolo.cesa-bianchi@unimi.it) Universit􀀒a degli Studi di Milano and Politecnico di Milano Milano, 20133, Italy Alberto Maria Metelli [albertomaria.metelli@polimi.it](albertomaria.metelli@polimi.it) Politecnico di Milano Milano, 20133, Italy Marcello Restelli [marcello.restelli@polimi.it](marcello.restelli@polimi.it) Politecnico di Milano Milano, 20133, Italy Editor: Tor Lattimore Abstract 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. Keywords: regret minimization, multi-armed bandits, expert advice, information theory, best of both worlds 1. Introduction The framework of multi-armed bandits (MAB) models sequential decision-making problems with partial feedback. Real-world applications of this framework span a wide array of domains and include problems such as dynamic pricing (Misra et al., 2019) and advert placement (Schwartz et al., 2017) . In the classical non-stochastic MAB problem (Auer et al. , 1995), a learner, faced with a 􀀌xed set of actions (also referred to as \arms"), repeatedly interacts with the environment in a series of rounds by selecting an action and subsequently 􀀍c2024 Khaled Eldowa, Nicol􀀒o Cesa-Bianchi, Alberto Maria Metelli, and Marcello Restelli. License: CC-BY 4.0, see [https://creativecommons.org/licenses/by/4.0/](https://creativecommons.org/licenses/by/4.0/. Attribution)[. Attribution](https://creativecommons.org/licenses/by/4.0/. Attribution) requirements are provided at [http://jmlr.org/papers/v25/24-0227.html](http://jmlr.org/papers/v25/24-0227.html). Eldowa, Cesa-Bianchi, Metelli, and Restelli observing a numerical loss assigned beforehand to this action. The performance of the learner is measured via the notion of regret, which compares the cumulative loss of the learner with that of the best action in hindsight. The minimax regret for this p

FAQs

What is the mediator feedback problem studied in the paper?

It is a bandit game where the learner selects a policy from a set, then observes an outcome sampled from that policy’s distribution and suffers the loss associated with the observed outcome in the current round.

How does the paper measure the complexity of a policy set?

It introduces policy set capacity as an information-theoretic measure capturing how complex the policy set is.

What regret guarantees are provided and under which settings?

Using the classical EXP4 algorithm, the paper provides new regret bounds that depend on policy set capacity in both adversarial and stochastic settings, and it also proves nearly-matching lower bounds for chosen policy families.

Aug 2, 2026

Upload by Ezra