Near-Linear MIR Algorithms for Stochastically-Ordered Priors

Gal Bahar, Omer Ben-Porat, Kevin Leyton-Brown, Moshe Tennenholtz · 2025

Read Near-Linear MIR Algorithms for Stochastically-Ordered Priors by Gal Bahar, Omer Ben-Porat, Kevin Leyton-Brown, Moshe Tennenholtz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12766.txt.

Introduction

Gal Bahar, Omer Ben-Porat, Kevin Leyton-Brown, and Moshe Tennenholtz present a 2025 paper on fair exploration in recommender systems. A recommender that experiments on users must keep each user's payoff at least as good as their default choice, a constraint called mechanism-informed individual rationality. Planning under it was possible but exponentially slow.

For the practical case where rewards follow a stochastic order, as with Gaussian or coin-flip outcomes, the authors find a near-linear algorithm. They recast the task as a goal Markov decision process and solve it by dynamic programming. Runtime drops to order K log K in the number of options, with no dependence on the reward support size. The result is asymptotically optimal for this class.

Catalog record

CREATORGal Bahar, Omer Ben-Porat, Kevin Leyton-Brown, Moshe Tennenholtz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE160 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12766

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Near-Linear MIR Algorithms for Stochastically-Ordered Priors Gal Bahar, Omer Ben-Porat, Kevin Leyton-Brown, Moshe Tennenholtz Abstract With the rise of online applications, recommender systems (RSs) often encounter constraints in balancing exploration and exploitation. Such constraints arise when exploration is carried out by agents whose utility must be taken into account when optimizing overall welfare. Recent work suggests that recommendations should be mechanism-informed individually rational (MIR) [ 6 ] . Specifically, if agents have a default arm they would use, relying on the RS should yield each agent at least the reward of the default arm, conditioned on the information available to the RS. Under the MIR constraint, striking a balance between exploration and exploitation becomes a complex planning problem. To that end, Bahar et al. [6] propose an approximately optimal yet inefficient planning algorithm that runs in O ⁡ ( 2 K ​ K 2 ​ H 2 ) O(2^{K}K^{2}H^{2}) , where K K is the number of arms and H H is the size of the support of the reward distributions. In this paper, we make a significant improvement for a special yet practical case, removing both the dependence on H H and the exponential dependence on K K . We assume a stochastic order of the rewards (e.g., Gaussian with unit variance, Bernoulli, etc.), and devise an asymptotically optimal algorithm with a runtime of O ⁡ ( K ​ log ⁡ K ) O(K\log K) . Our technique is based on formulating a Goal Markov Decision Process (GMDP), establishing an optimal dynamic programming procedure, and then unveiling its crux—fleshing out a simple index-based structure that facilitates efficient computation. Additionally, we present an incentive-compatible version of our algorithm. xplore-exploit, Recommender Systems, Individual Rationality, Incentive compatibility, Mechanism Design. 1 Introduction Multi-armed bandits (MABs) represent a fundamental problem in online learning. In this framework, the goal is to maximize total rewards by balancing the exploitation of known high-reward arms with the exploration of potentially better ones. With the rise of online applications, MAB scenarios often involve human-facing settings, where arms or rounds represent agents whose needs must be considered. For instance, several lines of work consider content providers as the arms [ 17 , 8 , 19 ] , requiring algorithms to incentivize the creation of high-quality content. In other works, beyond the exploration-exploitation dilemma, algorithms must also address fairness [ 20 , 24 ] , long-term welfare [ 9 , 28 ] , and strategic behavior [ 12 , 15 ] , among other concerns. A recent line of work initiated by Kremer et al. [23] considers MAB as a mechanism design problem [ 30 , 31 ] . In such settings, a recommender system suggests actions to agents without enforcing its choices. As agents are self-interested and may avoid high-risk, high-reward arms, there is a need to incentivize exploration to ensure accurate reward estimates for all arms. Previous works [ 25 , 27 , 14 ] achieve incentive compatibility (IC) by leveraging information asymmetry : While each agent possesses some prior information, mechanisms accumulate additional information by observing the actions and rewards of previous agents. Although IC typically serves as a benchmark for a mechanism’s trustworthiness, as it guarantees that agents maximize their expected utility by following the mechanism’s recommendations, mechanisms that employ information asymmetry still suffer from an inherent trust issue. Indeed, agents who receive recommendations that are deliberately suboptimal (i.e., exploration) may feel misled. One intuitive remedy is to modify the mechanism beyond mere IC by promising that an agent is never worse off by following a recommendation. This brings us to the classical notion of Individual Rationality (IR), or participation constraints [ 34 ] . IR requires that the expected utility from following the recommendation be at least as high as that of the agent’s default action—that is, the action they would select if the mechanism did not exist. Yet the standard IR definition inherits the same information-asymmetry pitfall: Because the mechanism holds more information than any single agent, it can propose actions that look rational from the agent’s perspective but are sub-optimal relative to the mechanism’s more comprehensive information. To address this issue, Bahar et al. [6] propose a stronger guarantee, Mechanism-informed Individual Rationality (MIR). 1 1 1 Bahar et al. [6] label this guarantee simply “IR.” To avoid confusion with the conventional IR constraint, we henceforth call it mechanism-informed IR. MIR requires that every recommendation’s expected reward, based on all the information available to the mechanism , meet or exceed the agent’s default-arm reward ex-ante . This stronger guarantee is crucial because it closes the information gap, treating the agent as if they possessed the mechanism’s accumulated information. Despite the attractiveness of MIR, relying on the mechanism’s accumulated information limits the ability to learn through exploration. Consequently, MIR mechanisms must adopt a careful exploration policy, maximizing their ability to explore risky arms while still satisfying the MIR guarantee by mixing low-risk and high-risk arms. Due to this challenge, prior work [ 6 ] faces significant practical limitations. Indeed, the runtime of the MIR mechanism of Bahar et al. [6] is O(2^{K}K^{2}H^{2}) , where K is the number of arms and H is the support size of the (discrete) reward distributions. This high runtime complexity severely limits the mechanism’s practicality, particularly when dealing with many arms or continuous reward distributions. For the latter, discretization approaches are either computationally infeasible or yield suboptimal rewards. In this paper, we revisit MIR constraints in Bayesian MABs with static rewards. For priors that are stochastically ordered , we design IREGB : An index-based algorithm that is MIR by construction and is asymptotically optimal among all MIR algorithms. Crucially, IREGB runs in O(K\log K) time—reducing the exponential 2^{K}K^{2} dependence on the number of arms down to near-linear and removing the H^{2} term entirely, so it works with continuous reward distributions. Finally, we use IREGB as a black-box to develop a MIR and IC algorithm. 1.1 Our Contribution We consider a MAB setting with a Bayesian prior and static rewards; that is, the reward of each arm is initially unknown and is realized only once. 2 2 2 This assumption allows us to focus on the novel mechanism-informed IR viewpoint proposed in this paper. A similar approach is taken by several early works on incentivizing exploration [ 4 , 6 ] , and some have strictly stronger assumptions, i.e., \{-1,1\} rewards [ 14 ] . Despite the limitation, our problem remains technically non-trivial. Some arms may be risky, having negative expected rewards but also offering high potential rewards. Additionally, we assume that there is a default arm that agents would pick if they did not use the algorithm. In each round, the algorithm picks a distribution over the arms, termed a portfolio . The algorithm then samples and selects an arm based on the portfolio’s weights. We aim to maximize social welfare, defined as the sum of rewards. Without any further constraints, maximizing welfare is straightforward: Pull each arm once, then repeatedly choose the best one. Due to our static rewards assumption, one round of exploration per arm is enough to reveal the highest reward. However, we restrict the algorithm to select only MIR portfolios. A portfolio is MIR if its expected

Read the complete text