Survey on multiplayer bandits, highlighting theoretical gaps and future directions.
problem Theoretical advancements in multiplayer bandits lack practical implementation in real-world scenarios.
method Organizes and contextualizes existing literature on multiplayer bandits.
result Clear directions for future research in adapting theoretical algorithms to real-world situations.
New algorithms improve dueling bandit performance in multiplayer settings.
problem Challenges in collaborative exploration of non-informative arm pairs in multiplayer dueling bandits.
method Demonstrated Follow Your Leader approach and message-passing fully distributed protocol.
result Multiplayer algorithms outperform single-player benchmarks.
New algorithm reduces regret in asynchronous multiplayer bandits to constant or logarithmic levels.
problem Asynchronous multiplayer bandits in cognitive radio networks.
method Cautious Greedy algorithm with O ( T log ( T ) ) \mathcal{O}(\sqrt{T\log(T)}) O ( T log ( T ) ) minimax regret. result Cautious Greedy yields constant instance-dependent regret under certain conditions.
A new algorithm reduces regret in multiplayer bandits with minimal communication.
problem Maximizing rewards in multiplayer multi-armed bandits with collisions.
method DPE (Decentralized Parsimonious Exploration) algorithm.
result Achieves the same regret as optimal centralized algorithms with less communication.
The paper tackles multi-player information asymmetry bandits in metric spaces.
problem Information asymmetry in rewards, actions, or both in multiplayer bandit problems.
method Adopted CAB and zooming algorithms for information asymmetry in rewards and actions.
result Regret bounds of the same order in all 3 problem settings.
New algorithm tackles multiplayer bandits with varying arm means, achieving optimal regret.
problem Stochastic multi-armed bandit problem with non-communicating players and collisions.
method Combines forced collisions for implicit communication and matching eliminations.
result First sublinear minimax regret bound of O ( ln ( T ) ) O(\ln(T)) O ( ln ( T )) for unique optimal assignment. We consider the problem of learning in single-player and multiplayer multiarmed bandit models. Bandit problems are classes of online learning problems that capture exploration versus exploitation tradeoffs. In a multiarmed bandit model, players can pick among many arms, and each play of an arm generates an i.i.d. rewar…
Paper develops efficient algorithms for learning rationalizable equilibria in multiplayer games.
problem Learning rationalizable behavior in multiplayer games under bandit feedback.
method New algorithms for finding rationalizable Coarse Correlated Equilibria and Correlated Equilibria with polynomial sample complexity.
result Achieved polynomial sample complexity for learning rationalizable equilibria, improving over existing exponential complexity.
Algorithm optimizes multi-player learning with noisy rewards without direct communication.
problem Cooperative multi-player learning with noisy rewards and no communication.
method Upper and lower confidence bounds algorithm for optimal action selection.
result Achieves logarithmic O ( log T Δ a ) O(\frac{\log T}{Δ_{\bm{a}}}) O ( Δ a l o g T ) and O ( T log T ) O(\sqrt{T\log T}) O ( T log T ) regret. Motivated by cognitive radio networks, we consider the stochastic multiplayer multi-armed bandit problem, where several players pull arms simultaneously and collisions occur if one of them is pulled by several players at the same stage. We present a decentralized algorithm that achieves the same performance as a centra…
We study multiplayer stochastic multi-armed bandit problems in which the players cannot communicate and if two or more players pull the same arm, a collision occurs and the involved players receive zero reward. We consider two feedback models: a model in which the players can observe whether a collision has occurred an…
Two new algorithms reduce group regret in abruptly changing multi-player bandit problems.
problem Reducing group regret in multi-player bandit problems in environments that change suddenly.
method Design of two novel algorithms: RR-SW-UCB# and SW-DLP.
result Expected cumulative group regret converges to zero over time.
Optimal channel assignment in ad hoc networks with heterogeneous users.
problem Optimal allocation of channels in a decentralized network with unknown and varying channel characteristics.
method Developed algorithms for explore-and-commit and logarithmic regret, leveraging specific user transmissions and sensing.
result Achieved near-optimal allocation with high probability and logarithmic regret, significantly outperforming state-of-the-art methods.
Paper tackles multiplayer symmetric games, securing equal share for n players.
problem Multiplayer games lack unique equilibria, making guarantees unreliable.
method Identifies conditions for equal share, designs efficient algorithms inspired by no-regret learning.
result Proves algorithms achieve approximate equal share across various settings.
New method finds Nash equilibria faster in multiplayer games.
problem Finding Nash equilibria in multi-player games, especially in noisy environments.
method Extra-gradient with player sampling and variance reduction.
result Proves better convergence rate than full extra-gradient for noisy games.
MpFL models clients as strategic players to reach equilibrium with less communication.
problem Real-world clients act independently with individual objectives, not aligned with a shared global model.
method MpFL uses game-theoretic modeling and PEARL-SGD algorithm for local updates and communication.
result PEARL-SGD reaches an equilibrium with less communication than non-local updates in stochastic setup.
V-learning tackles multiagent reinforcement learning by reducing sample complexity.
problem Curse of multiagents in multiagent reinforcement learning.
method V-learning is a fully decentralized algorithm that learns Nash, correlated, and coarse correlated equilibria.
result V-learning achieves sample complexity that scales with the maximum number of actions per agent, not the joint action space.
Recent progress in artificial intelligence through reinforcement learning (RL) has shown great success on increasingly complex single-agent environments and two-player turn-based games. However, the real-world contains multiple agents, each learning and acting independently to cooperate and compete with other agents, a…
Trading algorithms that execute large orders are susceptible to exploitation by order anticipation strategies. This paper studies the influence of order anticipation strategies in a multi-investor model of optimal execution under transient price impact. Existence and uniqueness of a Nash equilibrium is established unde…
Stochastic algo learns from evolving data, achieving optimal performance.
problem Performative prediction and multiplayer extensions.
method Stochastic approximation with decision-dependent distributions.
result Asymptotic normality and optimality of the algorithm's performance.
Gradient methods converge exponentially in concave network games.
problem Finding Nash equilibria in concave network zero-sum games.
method Gradient Ascent and Optimistic Gradient Ascent analyses.
result Exponential convergence rates in various game settings.
Paper proposes a method to predict MOBA game winners with calibrated confidence.
problem Predicting MOBA game winners with noisy data and uncertain noise.
method A novel confidence-calibration method considering data uncertainty.
result Achieves outstanding expected calibration error (ECE) of 0.57%.
Bayesian rating system for large competitions improves prediction and efficiency.
problem Rating systems for large, competitive events like online programming contests.
method Developed a Bayesian rating system for many participants, proving robustness and runtime.
result The system outperforms existing systems in accuracy and computation speed.
New algorithms tackle RKHS bandits with reduced complexity and improved performance.
problem Adversarial and stochastic RKHS bandit problems with high computational complexity.
method Combining approximation theory with misspecified linear bandit methods.
result First general algorithm for adversarial RKHS bandit problem.
Unified formulation bridges adversarial and nonstationary bandits.
problem Handling time-varying reward distributions in multi-armed bandit problems.
method Unified oracle that switches between adversarial and nonstationary bandit oracles based on window size.
result Optimal regret achieved with matching lower bound.
Paper studies attacks on bandit algorithms and shows how attackers can manipulate data to hijack behavior.
problem Potential attacks on bandit algorithms can cause catastrophic loss in real-world applications.
method Proposes a framework of offline and online attacks on bandit algorithms using convex optimization and adaptive strategies.
result Attackers can force bandit algorithms to pull target arms with high probability by manipulating data.
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . Paper tackles LDP bandits learning with improved results and sub-linear regret.
problem Contextual bandits learning with LDP privacy constraints.
method Simple black-box reduction frameworks for context-free bandits, extended to GLB.
result First result for BCO with multi-point feedback under LDP, sub-linear regret for GLB.
New algorithms for n-player games using a player-centered approach.
problem Learning near-perfect strategies in multiplayer games.
method Player-centered reinforcement learning with Final Adaptation RL.
result FARL is crucial for achieving near-perfect strategies in various games.
Algorithm identifies best arm in linked bandits with reduced feedback.
problem Best arm identification in linked bandits with reduced feedback.
method Combines uniform sampling with regular bandit algorithm.
result Almost matching upper and lower bounds on sample complexity.
Graph-Triggered Bandits unify rested and restless bandits with graph-defined arm interactions.
problem Modeling sequential decision-making problems with evolving arm rewards.
method Graph-Triggered Bandits (GTBs) framework that generalizes rested and restless bandits using a graph.
result Rested and restless bandits are special cases of GTBs for suitable graphs.
New definition resolves ambiguity in non-stationary bandit classification.
problem Ambiguity in classifying non-stationary bandits using existing definitions.
method Introducing a formal definition that resolves ambiguity and provides a unified approach.
result Unified approach applicable to both Bayesian and frequentist formulations, resolves classification issues.
Google Research Football: A new 3D physics-based game for reinforcement learning.
problem Training reinforcement learning algorithms in complex, realistic environments.
method Developed a new 3D physics-based football simulator environment.
result Reported baseline results for various reinforcement algorithms.
Unified approach for non-stationary and clustered bandits.
problem Solving non-stationary and clustered bandits with overlapping solutions.
method Test of homogeneity for seamless integration of non-stationary and clustered bandits.
result Unified solution framework for change detection and cluster identification.
A framework for auto-tuning hyper-parameters in contextual bandit algorithms.
problem Auto-tuning hyper-parameters in real-time for contextual bandit algorithms.
method Proposes a Syndicated Bandits framework to learn multiple hyper-parameters dynamically.
result Achieves optimal regret bounds under certain scenarios and handles multiple contextual bandit algorithms.
New algorithm learns optimal exploration parameters for contextual bandits.
problem Learning optimal exploration in contextual bandits.
method Proposes two algorithms that learn optimal exploration parameters online based on context and reward.
result Demonstrates improved performance in learning optimal exploration compared to traditional methods.
Investigates sequential problems on graph structures and large action spaces.
problem Sequential decision-making on graph structures and large action spaces.
method Spectral bandits, side observations, influence maximization, kernel bandits, polymatroid bandits, function optimization, infinitely many-arms bandits.
result Contributions to graph and structured bandits.
A new method for dueling bandits improves performance.
problem Improving decision-making in dueling bandits.
method Sup-KLUCB method for K-armed dueling bandits, converting Copeland dueling bandits into standard MAB problems.
result Sup-KLUCB outperforms state-of-the-art methods in Copeland dueling bandits.
Study on indexability of restless multi-armed bandits and rollout policy performance.
problem Maximizing discounted rewards in finite state restless multi-armed bandit problems.
method Decouple the problem into single-armed restless bandits, analyze using value iteration, and compare with Whittle index policy.
result Demonstrates conditions for indexability and compares performance of index policy and rollout policy.
New insights into multi-armed bandits with budget constraints.
problem Multi-armed bandits with supply/budget constraints.
method Characterization of logarithmic regret rates, simple regret, and reduction to other bandit problems.
result Full characterization of logarithmic, instance-dependent regret rates for BwK.
Optimal algorithm for identifying best arm in stochastic linear bandits with fixed confidence.
problem Identifying the best arm in stochastic linear bandits with fixed confidence.
method Extending an algorithm designed for Best Arm Identification to the ε ε ε -Thresholding Bandit Problem (TBP). result Asymptotically optimal algorithm for TBP.
A meta-UCB method combines stochastic bandit algorithms.
problem Combining multiple stochastic bandit algorithms efficiently.
method Meta-UCB procedure solving an N-armed bandit problem.
result Final regret depends only on the best base algorithm's regret.
New method for contextual bandits with corrupted context.
problem Contextual bandits with corrupted context in online settings.
method Combining contextual bandit and multi-armed bandit approaches.
result Improved learning from all iterations, including corrupted ones.
A new algorithm for top-k combinatorial bandits with full-bandit feedback.
problem Optimizing decisions among subsets of arms with only aggregate rewards observed.
method CSAR algorithm using Hadamard matrices for estimating individual arm rewards.
result Proved a tight lower bound on sample complexity for k = O ( 1 ) k=O(1) k = O ( 1 ) . A new framework for structured bandits using influence diagrams and variational Thompson sampling.
problem Complex statistical dependencies in structured bandit problems.
method Influence diagram framework, variational Thompson sampling, tracking structured posterior distribution.
result Empirically evaluated algorithms perform as well as or better than existing baselines.
Smooth Contextual Bandits bridge two previously studied extremes of non-differentiable and parametric-response bandits.
problem Nonparametric contextual bandits with Hölder smoothness.
method Developed a novel algorithm that optimally balances between non-differentiable and parametric-response bandits.
result Proved the algorithm achieves rate-optimal regret for all smoothness settings.
New algorithm for nonstationary multi-armed bandits with optimal performance.
problem Nonstationary multi-armed bandits with changing model parameters over time.
method Adaptive Resetting Bandit (ADR-bandit) algorithm using adaptive windowing techniques.
result ADR-bandit achieves nearly optimal performance in both abrupt and gradual changes.
First robust bandit algorithm for contextual bandits with sub-linear regret.
problem Vulnerability of linear contextual bandit algorithms to adversarial attacks.
method Proposes a robust bandit algorithm for stochastic linear contextual bandits under fully adaptive and omniscient attacks.
result Sub-linear regret under various attacks without requiring attack information.