New insights link no-regret learning to online conformal prediction in adversarial settings.
problem Understanding the relationship between no-regret learning and online conformal prediction in adversarial environments.
method Analysis of existing algorithms and new connections between no-regret learning and conformal prediction.
result No-regret learning algorithms can provide group-conditional coverage guarantees in adversarial settings.
New algorithm balances exploration cost between groups in multi-armed bandits.
problem Balancing exploration cost between groups in multi-armed bandits.
method Introducing Col-UCB algorithm that dynamically coordinates exploration across groups.
result Achieves optimal minimax and instance-dependent collaborative regret up to logarithmic factors.
New algorithms achieve small prediction regret for learning from overlapping groups.
problem Online multi-group learning with fairness applications.
method Oracle-efficient algorithms for groups not explicitly enumerated.
result Sublinear regret in various settings.
Study collaborative learning among multi-agents in multi-armed bandits.
problem Minimizing group cumulative regret in a heterogeneous multi-agent setting.
method Developed decentralized algorithms for collaboration between N N N agents learning M M M stochastic multi-armed bandits. result Proved near-optimal behavior of proposed algorithms for group regret.
New algorithm reduces individual regret and communication costs in cooperative bandits.
problem Optimal individual and group regret in cooperative multi-agent bandits.
method Integrates a new communication policy into a learning algorithm.
result Achieves optimal individual regret and constant communication costs.
Adaptive designs achieve strong Neyman regret guarantees for ATE estimation.
problem Estimating unbiased average treatment effect in sequential experiments.
method Proposed adaptive designs with O ~ ( log T ) \widetilde{O}(\log T) O ( log T ) Neyman regret under boundedness assumptions and O ~ ( T ) \widetilde{O}(\sqrt{T}) O ( T ) multigroup Neyman regret in covariate-based settings. result Adaptive designs outperform non-adaptive designs in terms of Neyman regret, especially in covariate-based settings.
Study invariant Lipschitz bandits, improving regret bounds.
problem Optimizing decisions under symmetry in online settings.
method Integrates side observations using group orbits into UniformMesh algorithm.
result Improved regret bound for invariant Lipschitz bandit class.
The study quantifies decision-making risks from suboptimal classifiers and proposes methods to reduce these risks.
problem Excess risk in decision-making from suboptimal probabilistic classifiers.
method Analytical expressions and upper/lower bounds for excess risk, calibration curve estimation, grouping loss estimator.
result Identifies regimes where recalibration alone or post-training is more effective.
This paper addresses dynamic price discrimination with fairness constraints.
problem Dynamic price discrimination with fairness constraints in online retailing.
method Nonparametric demand models, dynamic pricing policy, regret minimization.
result Optimal dynamic pricing policy with i l d e O ( T 4 / 5 ) ilde{O}(T^{4/5}) i l d e O ( T 4/5 ) regret for price fairness. New algorithms allocate sampling budget to estimate group means without exploration.
problem Allocate sampling budget to estimate means of multiple groups.
method Design exploration-free non-adaptive and adaptive algorithms.
result Prove tighter regret bounds for multi-group mean estimation.
Adaptive clustering and personalization algorithms minimize regret in multi-agent stochastic linear bandits.
problem Minimizing regret in a multi-agent stochastic linear bandits framework with user heterogeneity.
method Proposes a novel algorithm that refines cluster identities and minimizes regret, adapting to cluster separation and user parameter deviations.
result Regret scales as O ( T / N ) \mathcal{O}(\sqrt{T/N}) O ( T / N ) for well-separated clusters and O ( T 1 2 + ε / ( N ) 1 2 − ε ) \mathcal{O}(T^{\frac{1}{2} + \varepsilon}/(N)^{\frac{1}{2} -\varepsilon}) O ( T 2 1 + ε / ( N ) 2 1 − ε ) for poorly separated clusters. Doubly fair dynamic pricing ensures equal prices for different groups over time.
problem Achieving equal prices for different groups in online dynamic pricing.
method Online learning algorithm that balances procedural and substantive fairness.
result Achieves i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret, zero procedural unfairness, and i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) substantive unfairness. The paper tackles fair sharing of exploration costs across groups in online learning.
problem Sharing the cost of exploration fairly across multiple groups in online learning.
method The paper introduces the 'grouped' bandit model and uses axiomatic bargaining theory, specifically the Nash bargaining solution, to formalize fairness.
result The paper derives policies that are optimally fair and regret-optimal, showing that regret-optimal policies can be unfair.
New framework tackles stochastic latent subgroup heterogeneity in online decision-making.
problem Stochastic latent heterogeneity in online decision-making where individual responses vary with unobserved subgroups.
method Latent heterogeneous bandit framework using EM-greedy algorithm to learn subgroup probabilities and reward parameters.
result Achieves optimal estimation and classification guarantees, revealing a fundamental stochastic barrier in online decision-making.
A new algorithm reduces frequentist regret in multi-agent bandit problems with sparse hypergraphs.
problem Deriving a frequentist regret bound for Thompson sampling in multi-agent settings with sparse hypergraphs.
method Proposed ε ε ε -exploring Multi-Agent Thompson Sampling ( ε ε ε -MATS) algorithm that combines exploration and exploitation strategies. result Achieves a worst-case frequentist regret bound sublinear in time horizon and local arm size, optimal up to constants and logarithms for sparse hypergraphs.
New algorithm for bandits with delayed action effects, reducing regret.
problem Delayed impact of actions in multi-armed bandits.
method Formulated a new bandit setting with delayed action effects, proposed an algorithm with regret bound.
result Achieved a regret of i l d e O ( K T 2 / 3 ) ilde{\mathcal{O}}(KT^{2/3}) i l d e O ( K T 2/3 ) and showed a matching lower bound. A new reinforcement learning framework separates users into risk-tolerant and risk-averse groups for better performance.
problem Improving performance for risk-averse users in reinforcement learning.
method Introducing a tiered reinforcement learning approach with two policies: π e x t O π^{ ext{O}} π e x t O and π e x t E π^{ ext{E}} π e x t E . result Achieving constant regret for risk-averse users, independent of the number of episodes.
ComEx protocol reduces communication costs in cooperative bandits.
problem Minimizing communication costs in cooperative bandits while maintaining optimal performance.
method Developed ComEx protocol to reduce communication from Θ ( T ) Θ(T) Θ ( T ) to O ( log T ) O(\log T) O ( log T ) messages. result Achieves state-of-the-art performance with significantly reduced communication cost.
Algorithm maximizes user rewards under per-item budget constraints.
problem Maximizing cumulative rewards in collaborative bandits with budget constraints.
method Collaborative algorithm B-LATTICE that clusters users and collaborates across groups.
result Achieves sub-linear regret bounds matching minimax bounds.
Two new algorithms reduce online kernel regression's computational cost while maintaining optimal regret bounds.
problem Trade-off between regret and computational cost in online kernel regression.
method AOGD-ALD and NONS-ALD algorithms dynamically maintain nearly orthogonal basis to approximate kernel mapping and control approximate error.
result Achieves nearly optimal regret bounds at sublinear computational complexity.
The paper tackles a bandit problem with infinitely many arms per group, aiming to identify the group with the highest quantile reward.
problem Max-quantile group bandit problem with infinitely many arms per group.
method Two-step algorithm: first request arms from each group, then apply a finite-arm max-quantile bandit algorithm.
result Characterization of instance-dependent and worst-case regret, with matching lower bounds.
New algorithm minimizes regret in multi-agent bandit problem with probabilistic communication.
problem Minimizing group regret in multi-agent multi-armed bandit problem with probabilistic communication.
method Proposes a new UCB-based algorithm for decentralized multi-agent multi-armed bandit problem on d d d -regular graphs with probabilistic communication. result The proposed algorithm outperforms state-of-the-art algorithms in minimizing group regret.
Study cooperative bandit learning with imperfect communication, achieving near-optimal performance.
problem Real-world distributed decision-making with imperfect communication.
method Proposed decentralized algorithms for three communication scenarios: stochastic networks, random delays, and adversarially corrupted rewards.
result Achieved competitive performance and near-optimal guarantees on group regret.
Improved regret bounds for structured linear contextual bandits with Gaussian noise.
problem Optimizing bandit learning algorithms for structured contexts with Gaussian perturbations.
method Proposed simple greedy algorithms for structured linear contextual bandits with Gaussian noise.
result Unified regret analysis for structured parameters with geometric quantities as bounds.
A new algorithm balances global reward and group constraints in federated multi-armed bandits.
problem Maximizing global reward while protecting client privacy in federated learning.
method Combinatorial contextual bandit with group constraints, using a two-output Gaussian process.
result TCGP-UCB incurs low regret, balancing super arm reward and group reward constraints.
Study on a new family of problems interpolating expert advice and multi-armed bandits.
problem A new family of problems combining expert advice and multi-armed bandits.
method Proved minimax regret bounds and designed optimal PAC algorithms for pure exploration.
result Tight minimax regret bounds and optimal PAC algorithm for m \mathbf{m} m -BAI. Kernel method improves cooperative decision-making among agents.
problem Cooperative multi-agent decision making with contextual information.
method Proposed extsc{Coop-KernelUCB} algorithm for near-optimal per-agent regret.
result Near-optimal bounds on per-agent regret with efficient computation and communication.
This work improves privacy in federated combinatorial bandits by balancing regret and privacy.
problem Privacy-preserving learning in competitive online learning settings with quality constraints.
method Proposes P-FCB algorithm for federated combinatorial bandits, balancing regret and privacy.
result Improves regret while maintaining quality constraints and privacy guarantees.
AGG-UCB uses neural networks to optimize group behaviors in contextual bandits.
problem Optimizing group behaviors in contextual bandits with mutual impacts.
method Introduces Arm Group Graph (AGG) and AGG-UCB algorithm using neural networks and graph neural networks.
result Achieves near-optimal regret bound with over-parameterized neural networks.
We analyze how batch learning impacts bandit problems.
problem Impact of batch learning in stochastic bandits.
method Policy-agnostic regret analysis, upper and lower bounds demonstration.
result The impact of batch learning can be measured in terms of online behavior.
We consider a collaborative online learning paradigm, wherein a group of agents connected through a social network are engaged in playing a stochastic multi-armed bandit game. Each time an agent takes an action, the corresponding reward is instantaneously observed by the agent, as well as its neighbours in the social n…
The paper addresses fairness in dynamic pricing for strategic buyers.
problem Price disparities among specific groups can lead to unfair perceptions and legal violations.
method Proposes a dynamic pricing policy that achieves fairness and discourages strategic behavior.
result Achieves an upper bound of O ( T + H ( T ) ) O(\sqrt{T}+H(T)) O ( T + H ( T )) regret over T T T time horizons, reducing regret by 35.06% compared to a benchmark policy. Bayesian optimization gains efficiency by leveraging symmetries through a modified max kernel.
problem Improving Bayesian optimization efficiency for functions with group symmetries.
method Developed a PSD projection of the max kernel to exploit symmetries without violating kernel properties.
result The modified max kernel achieves lower regret compared to existing invariant and non-invariant kernels.
New protocol reduces communication costs for heterogeneous bandits over complex networks.
problem Minimizing group regret in a multi-agent, heterogeneous bandit setting over complex networks.
method Flooding with Absorption (FwA) protocol for heterogeneous bandits over complex networks.
result FwA protocol significantly reduces communication costs compared to flooding while maintaining similar regret performance.
Algorithm learns from changing zero-sum games with no regret.
problem Learning in time-varying zero-sum games.
method Developed a single parameter-free algorithm with three performance measures.
result Algorithm recovers best known results for fixed games and adapts to non-stationarity.
Unified framework for high-dimensional bandit problems with low-dimensional structures.
problem Stochastic high-dimensional bandit problems with low-dimensional structures.
method Proposed a simple unified algorithm and a general analysis framework for the regret upper bound.
result Unified algorithm achieves comparable regret bounds in various high-dimensional bandit problems.
In many real life situations, including job and loan applications, gatekeepers must make justified and fair real-time decisions about a person's fitness for a particular opportunity. In this paper, we aim to accomplish approximate group fairness in an online stochastic decision-making process, where the fairness metric…
Proposes a method to improve CATE estimation by imputing missing potential outcomes.
problem Statistical discrepancy between distinct treatment groups in CATE estimation.
method Contrastive learning approach to reliably impute missing potential outcomes for a subset of individuals.
result Improves the accuracy and robustness of CATE estimation models.
Develops robust learning methods for datasets with sub-populations.
problem Robust performance and generalization to unseen testing populations in datasets with sub-populations.
method Min-max-regret (MMR) formulation for distribution-free robust hierarchical model.
result Empirical MMR enjoys regret guarantees on training and unseen testing populations.
Decentralized algorithm reduces regret and converges to Nash equilibrium in online congestion games.
problem Online congestion games with exponential action sets and strict Nash equilibria.
method CongestEXP algorithm using exponential weights method.
result CongestEXP achieves O ( k F T ) O(kF\sqrt{T}) O ( k F T ) regret bound and almost exponential convergence to strict Nash equilibrium. The paper tackles cooperative RL with function approximation, achieving near-optimal learning with limited communication.
problem Cooperative multi-agent reinforcement learning with function approximation.
method Careful message-passing and cooperative value iteration.
result Achieving near-optimal no-regret learning with limited communication in cooperative multi-agent settings.
We develop a novel family of algorithms for the online learning setting with regret against any data sequence bounded by the empirical Rademacher complexity of that sequence. To develop a general theory of when this type of adaptive regret bound is achievable we establish a connection to the theory of decoupling inequa…
Optimal algorithm for latent bandits with cluster structure reduces regret to nearly optimal.
problem Maximizing cumulative rewards in a multi-armed bandit problem with latent clusters.
method LATTICE algorithm exploiting cluster structure and arm information.
result Minimax optimal regret of O ( ( M + N ) T ) O(\sqrt{(\mathsf{M}+\mathsf{N})\mathsf{T}}) O ( ( M + N ) T ) with O ( log T ) O(\log{\mathsf{T}}) O ( log T ) calls to matrix completion oracle. We study the multi-player stochastic multiarmed bandit (MAB) problem in an abruptly changing environment. We consider a collision model in which a player receives reward at an arm if it is the only player to select the arm. We design two novel algorithms, namely, Round-Robin Sliding-Window Upper Confidence Bound\# (RR-…
A new algorithm reduces regret in cooperative multi-agent bandits with heavy-tailed data.
problem Cooperative multi-agent bandits with heavy-tailed data.
method MP-UCB algorithm incorporating robust estimation with message-passing protocol.
result Optimal regret bounds for MP-UCB in various settings.
Regret minimization is treated as the golden rule in the traditional study of online learning. However, regret minimization algorithms tend to converge to the static optimum, thus being suboptimal for changing environments. To address this limitation, new performance measures, including dynamic regret and adaptive regr…
Study symmetric linear bandits with hidden symmetry, achieving improved regret bounds.
problem High-dimensional linear bandits with hidden symmetry.
method Model selection within low-dimensional subspaces to learn hidden symmetry.
result Achieved improved regret bounds of O ( d 0 2 / 3 T 2 / 3 log ( d ) ) O(d_0^{2/3} T^{2/3} \log(d)) O ( d 0 2/3 T 2/3 log ( d )) and O ( d 0 T log ( d ) ) O(d_0\sqrt{T\log(d)} ) O ( d 0 T log ( d ) ) . The paper analyzes the sliding regret of stochastic bandit algorithms.
problem Measuring the one-shot behavior of no-regret algorithms in stochastic bandits.
method Introducing sliding regret to measure the worst pseudo-regret over a time-window.
result Randomized methods have optimal sliding regret, while index policies have the worst possible sliding regret.