Paper analyzes sample complexity of offline MABs with KL regularization.
problem Optimizing sample complexity for offline decision-making with KL-regularized metrics.
method Sharp analysis of KL-PCB, providing upper and lower bounds.
result Characterizes sample complexity for offline MABs with KL regularization.
New method uses offline data to improve online bandit learning, even when distributions differ.
problem Improving online bandit learning with different offline and online distributions.
method MIN-UCB policy that adapts to offline data when informative, achieving tight regret bounds.
result MIN-UCB policy outperforms UCB policy with offline data and provides tight regret bounds.
New algorithms improve decision-making with limited offline data.
problem Using limited offline data to cluster users for better decision-making.
method Proposed two algorithms: Off-C2LUB and Off-CLUB to address data insufficiency.
result Both algorithms outperform existing methods under limited offline user data.
Paper tackles stochastic k k k -submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k k k -submodular functions with full-bandit feedback. method Proposes online algorithms for various k k k -submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α α α -regret bounds for multiple k k k -submodular stochastic combinatorial multi-armed bandit problems. Proposes a fair RMAB framework ensuring equal exposure to arms.
problem Fairness in RMABs where arms are not equally exposed.
method Defines merit of each arm based on stationary reward distribution and ensures equal exposure in proportion to merit.
result Achieves sublinear fairness regret of O ( T ln T ) O(\sqrt{T\ln T}) O ( T ln T ) in single pull case. New policy for non-stationary multi-armed bandits with recovering rewards.
problem Non-stationary multi-armed bandits with recovering rewards.
method Purely Periodic Policies integrating upper confidence bound procedure.
result Approximately O ~ ( N T ) \widetilde{\mathcal O}(N\sqrt{T}) O ( N T ) regret against the offline benchmark. In data-limited settings, stochastic policies can outperform deterministic ones in bandit problems.
problem Making reliable decisions with limited data in bandit problems.
method Designing TRUST, an algorithm that uses localization laws and relative pessimism.
result TRUST achieves comparable sample complexity to LCB on minimax problems but is significantly lower on few-sample problems.
This work explores the idea of a causal contextual multi-armed bandit approach to automated marketing, where we estimate and optimize the causal (incremental) effects. Focusing on causal effect leads to better return on investment (ROI) by targeting only the persuadable customers who wouldn't have taken the action orga…
New principle optimizes bandit decisions with context.
problem Dealing with general function classes and large context spaces in bandits.
method Upper Counterfactual Confidence Bounds (UCCB) principle.
result Proves optimality and efficiency in complex settings.
New algorithms improve performance guarantees for multi-armed bandits problems.
problem Allocating effort under uncertainty in scenarios like investing research effort.
method Proposed two new families of bandit algorithms with stronger guarantees.
result Achieved optimal dependence on k with additional properties of arm reward curves.
New framework for resilient bi-criteria optimization under noisy feedback.
problem Bi-criteria combinatorial optimization with noisy function evaluations.
method Introducing ( α , β , δ , e x t t t N ) (α,β,δ, exttt{N}) ( α , β , δ , e x ttt N ) -resilience and developing a black-box framework. result Achieves sublinear regret and constraint violation for bi-criteria bandit problems.
A new bandit algorithm observes arm rewards before playing, reducing regret.
problem Balancing exploration and exploitation with pre-observation costs.
method Design of OBP-UCB for single-player and C-MP-OBP for multi-player settings.
result Proved regret bounds for both single-player and multi-player settings.
KL-MS improves regret bounds for multi-armed bandits with bounded rewards.
problem Designing efficient exploration algorithms for multi-armed bandits with bounded rewards.
method Kullback-Leibler Maillard Sampling (KL-MS) for multi-armed bandits with bounded rewards.
result KL-MS achieves a worst-case regret bound of O ( μ ∗ ( 1 − μ ∗ ) K T ln K + K ln T ) O(\sqrt{μ^*(1-μ^*) K T \ln K} + K \ln T) O ( μ ∗ ( 1 − μ ∗ ) K T ln K + K ln T ) . We consider the stochastic multi-armed bandit problem and the contextual bandit problem with historical observations and pre-clustered arms. The historical observations can contain any number of instances for each arm, and the pre-clustering information is a fixed clustering of arms provided as part of the input. We de…
A graph bandit algorithm learns optimal paths on unknown graphs.
problem Optimal path selection on unknown graphs under uncertainty.
method G-UCB algorithm based on offline graph planning and optimism principle.
result Achieves tight regret bound of O ( ∣ S ∣ T log ( T ) + D ∣ S ∣ log T ) O(\sqrt{|S|T\log(T)}+D|S|\log T) O ( ∣ S ∣ T log ( T ) + D ∣ S ∣ log T ) . Over the past decade, contextual bandit algorithms have been gaining in popularity due to their effectiveness and flexibility in solving sequential decision problems---from online advertising and finance to clinical trial design and personalized medicine. At the same time, there are, as of yet, surprisingly few options…
Optimal policy for multi-armed multi-action bandits with unknown parameters.
problem Optimal sequential action selection for multi-armed multi-action bandits with unknown parameters.
method Occupancy-Measured-Reward Index Policy (OMRIP) and R(MA)^2B-UCB algorithm.
result Asymptotically optimal policy with sub-linear regret and low computational complexity.
A new offline RL framework unifies imitation learning and vanilla offline RL.
problem Learning from expert datasets without active data collection.
method A new offline RL framework that interpolates between imitation learning and vanilla offline RL, using a weak concentrability coefficient and a lower confidence bound algorithm.
result LCB algorithm achieves a faster rate of 1 / N 1/N 1/ N for nearly-expert datasets, and is adaptively optimal for the entire data composition range. Stochastic multi-armed bandits form a class of online learning problems that have important applications in online recommendation systems, adaptive medical treatment, and many others. Even though potential attacks against these learning algorithms may hijack their behavior, causing catastrophic loss in real-world appli…
Optimized Sharpe Ratio for better risk-adjusted decision-making in multi-armed bandits.
problem Challenging to optimize Sharpe Ratio (SR) in multi-armed bandits (MAB) due to constant regret.
method Proposed UCB-RSSR algorithm for RSSR maximization, derived path-dependent concentration bound and regret guarantees.
result UCB-RSSR outperforms existing algorithms and finds applications in risk-aware portfolio management.
New algorithm uses machine learning to predict rewards for decision-making problems.
problem Sequential decision-making under uncertainty with scarce online data.
method Machine Learning-Assisted Upper Confidence Bound (MLA-UCB) algorithm.
result Proves to improve cumulative regret even with biased surrogate rewards.
New dynamic allocation methods for multi-armed bandit models.
problem Dynamic allocation problems in multi-armed bandit models.
method New types of dynamic allocation problems and proofs for Gittins index decomposition.
result New proofs for Gittins index decomposition and related results.
The (contextual) multi-armed bandit problem (MAB) provides a formalization of sequential decision-making which has many applications. However, validly evaluating MAB policies is challenging; we either resort to simulations which inherently include debatable assumptions, or we resort to expensive field trials. Recently …
PAC-Bayesian analysis improves lifelong learning in multi-armed bandits.
problem Improving lifelong learning in multi-armed bandits.
method PAC-Bayesian analysis for deriving lower bounds and proposing lifelong learning algorithms.
result Proposed algorithms outperform baseline methods in lifelong multi-armed bandit problems.
Algorithm balances online and offline data for linear bandits.
problem Online learning with an offline dataset in linear bandits.
method Proposes a linear bandit algorithm that uses offline data early and increasingly favors exploration as the horizon grows.
result Establishes regret bounds showing competitive performance with both purely online and offline solutions.
New algorithm minimizes regret in multi-armed bandits with network interference.
problem Minimizing regret in online experiments with network interference.
method Sparse network interference model, discrete Fourier analysis, linear regression-based algorithms.
result Provable low regret algorithms for sparse interference networks.
Paper uses subjective logic to estimate uncertainty in multi-armed bandit problems.
problem Estimating uncertainty in multi-armed bandit problems.
method Formalism of subjective logic applied to multi-armed bandits, proposing new algorithms.
result Subjective logic quantities enable useful assessment of uncertainty.
Algorithm improves multi-armed bandit performance by transferring reward samples.
problem Sequential multi-armed bandit problem with changing reward distributions.
method UCB algorithm with reward sample transfer.
result Significant improvement in cumulative regret over standard UCB.
Quantum algorithms for multi-armed bandits are explored with limited reward access.
problem Exploring quantum speed-ups in multi-armed bandit problems with limited reward information.
method Introduced new bandit models and showed query complexity equivalence with classical algorithms.
result No quadratic speed-up is possible for multi-armed bandits with limited reward access.
Study on Pareto optimality in multi-objective bandit problems.
problem Pareto optimality in multi-objective multi-armed bandit problems.
method Formulated adversarial multi-objective multi-armed bandit, defined Pareto regrets, presented algorithms, established upper and lower bounds.
result New algorithms are optimal in adversarial settings and nearly optimal in stochastic settings.
Framework reduces contextual bandit learning to offline regression with near-optimal regret.
problem Efficient learning with large action spaces and complex reward functions.
method Offline Estimation to Decisions (OE2D) algorithm that minimizes regret with near-optimal oracle calls.
result Near-optimal regret for contextual bandits with large action spaces and O ( l o g ( T ) ) O(log(T)) O ( l o g ( T )) offline oracle calls. 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.
New ranking algorithms improve online content delivery by learning from click data.
problem Bias in ranking systems due to production system biases.
method Proposed novel extensions of LinUCB and Linear Thompson Sampling algorithms to handle position-based click model.
result Validated the proposed algorithms through offline and online experiments.
In this paper we propose a multi-armed bandit inspired, pool based active learning algorithm for the problem of binary classification. By carefully constructing an analogy between active learning and multi-armed bandits, we utilize ideas such as lower confidence bounds, and self-concordant regularization from the multi…
The paper tackles lifelong learning in multi-armed bandits, aiming to minimize average regret over multiple tasks.
problem Minimizing average regret in multi-armed bandits over multiple tasks.
method Confidence interval tuning of UCB algorithms and greedy algorithms applied to a bandit over bandit approach.
result Empirical improvement over previous work in the mortal bandit problem.
Study finds optimal regret bound for multi-armed bandit problem with expert advice.
problem Optimizing decision-making in a multi-armed bandit problem with expert advice.
method Proved a tight lower bound matching the upper bound of Kale (2014) for minimax expected regret.
result The minimax optimal expected regret is Θ(√(T K log (N/K))) for the problem.
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden simple multi-armed bandit structure in which the rewards are independent of the contextual information. Algorithms that are designed solely for one of the regimes are known to be sub-optimal for the alternate regime…
Faster algorithm reduces contextual bandit regret with fewer offline regression calls.
problem Optimizing reward in contextual bandits with unknown functions.
method Designing a simple algorithm with O ( log T ) {O}(\log T) O ( log T ) offline regression calls. result Achieves statistically optimal regret with minimal offline calls.
New method for identifying best arm in batched multi-armed bandit problems.
problem Identifying the best arm in multi-armed bandit problems where arms are sampled in batches.
method General linear programming framework for best arm identification in batched multi-armed bandit problems.
result Demonstrated good performance in numerical studies compared to UCB-type or Thompson sampling methods.
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.
OE2D framework reduces contextual bandits to offline regression for near-optimal regret.
problem Efficiently learning contextual bandits with large action spaces and complex reward functions.
method Offline Estimation to Decisions (OE2D) algorithm that reduces contextual bandits to offline regression.
result Near-optimal regret for contextual bandits with large action spaces and O ( log T ) O(\log T) O ( log T ) calls to an offline regression oracle. The paper explores sampling problems and shows minimal exploration is needed.
problem Exploration-exploitation trade-off in sampling.
method Systematic definition of regret, proposal of a simple algorithm.
result Near-optimal regret bounds achieved with minimal exploration.
This paper improves offline contextual bandits using distributional robustness.
problem Improving offline contextual bandits with robustness.
method Extends Distributionally Robust Optimization (DRO) for offline contextual bandits, introducing a convex reformulation of Counterfactual Risk Minimization.
result Automatic calibration of asymptotic confidence intervals for policy optimization.
Proposes a method to learn from historical data for personalized decision-making.
problem Sample hunger in sequential decision-making algorithms for personalized medicine.
method Identifiable latent bandit framework using nonlinear independent component analysis.
result Optimal decision-making with shorter exploration time than classical bandits.
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.
Unified approach to correlated multi-armed bandits reduces regret significantly.
problem Correlated rewards in multi-armed bandits.
method Developed a unified approach to leverage reward correlations and presented algorithms with rigorous analysis.
result C-UCB algorithm pulls non-competitive arms only O(1) times, improving over classic algorithms.
Paper tackles transfer learning for contextual multi-armed bandits under covariate shift.
problem Nonparametric contextual multi-armed bandits with covariate shift.
method Established minimax rate of convergence, proposed transfer learning algorithm.
result Achieved near-optimal statistical guarantees for learning in target domain.
Study linear contextual bandits with confounded offline data, improving regret bounds.
problem Linear contextual bandits with confounded offline data.
method Construct a linear bandit algorithm that utilizes projected information.
result Proved regret bounds that improve current bounds by a factor related to visible dimensionality.