Study optimal arms in combinatorial bandits with semi-bandit feedback and finite budget.
problem Finding optimal arms in combinatorial bandits with semi-bandit feedback and finite budget constraints.
method Proposes a generic algorithm covering various arm elimination strategies and derives lower bounds.
result Demonstrates sufficient and necessary budget requirements for finding the best arm.
New algorithm for countable bandits with optimal regret.
problem Stochastic bandit problem with countably many arms.
method Fully adaptive online learning algorithm with O(log n) expected cumulative regret.
result Achieves optimal regret of O(log n) after any number of plays n.
This paper studies the problem of identifying any k k k distinct arms among the top ρ ρ ρ fraction (e.g., top 5\%) of arms from a finite or infinite set with a probably approximately correct (PAC) tolerance ε ε ε . We consider two cases: (i) when the threshold of the top arms' expected rewards is known and (ii) when it is unk…
FP-UCB algorithm achieves bounded regret for finitely parameterized multi-armed bandits.
problem Finitely parameterized multi-armed bandits with unknown but known parameter set.
method FP-UCB algorithm using structural information about the parameter set.
result FP-UCB achieves bounded regret under structural condition, logarithmic otherwise.
Algorithm reduces regret in restless multi-armed bandits by adaptively sequencing arm choices.
problem Minimizing regret in restless multi-armed bandits with unknown dynamics.
method Adaptive Sequencing Rules (ASR) algorithm that selects arms in a consecutive manner.
result Achieves logarithmic regret order with time and finite-sample bound.
The paper tackles linear bandits with projections, achieving optimal regret.
problem Learning the best arm in a linear bandit model with unobservable projection rewards.
method Developed strategies for both finite and infinite arms, achieving optimal regret bounds.
result Achieved optimal regret bounds for both finite and infinite arms.
In this paper, we study multi-armed bandit problems in explore-then-commit setting. In our proposed explore-then-commit setting, the goal is to identify the best arm after a pure experimentation (exploration) phase and exploit it once or for a given finite number of times. We identify that although the arm with the hig…
Study best arm identification in restless bandits with unknown TPMs.
problem Identify the best arm with fixed confidence in restless bandits with unknown TPMs.
method Proposed a policy for best arm identification and proved its expected stopping time matches the lower bound.
result The state-action visitation proportions match the optimal proportions under any asymptotically optimal policy.
An optimal algorithm for multi-armed bandits with constraints.
problem Optimizing decisions in constrained multi-armed bandit problems.
method An index-based deterministic algorithm using Locatelli's anytime thresholding under known optimal value assumption.
result The algorithm achieves asymptotic optimality with probability approaching 1.
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 algorithm for shareable arms with load-dependent rewards in stochastic bandits.
problem Learning optimal play strategy with shareable finite-capacity arms in stochastic bandits.
method Developed a capacity estimator and online learning algorithm for MP-MAB with shareable arms.
result Regret upper bound matches the lower bound, validating the algorithm's performance.
We consider the best-arm identification problem in multi-armed bandits, which focuses purely on exploration. A player is given a fixed budget to explore a finite set of arms, and the rewards of each arm are drawn independently from a fixed, unknown distribution. The player aims to identify the arm with the largest expe…
New Thompson sampling algorithm reduces regret for exponential family bandits.
problem Minimizing regret in multi-armed bandit problems with exponential family rewards.
method Proposes ExpTS and ExpTS + ^+ + algorithms using novel sampling distributions. result Minimizes both finite-time and asymptotic regret for exponential family rewards.
Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing techniques for finite-armed bandits, notably the optimism principle and Thompson sampling. While prior work has mostly been in the worst-case …
We consider the problem of identifying any k k k out of the best m m m arms in an n n n -armed stochastic multi-armed bandit. Framed in the PAC setting, this particular problem generalises both the problem of `best subset selection' and that of selecting `one out of the best m' arms [arcsk 2017]. In applications such as crowd…
New method for semiparametric bandits reduces regret to optimal levels.
problem Complex reward structures in semiparametric bandits.
method Experimental-design approach with sharp regret bound and PAC bound.
result Minimax regret of i l d e O ( d T ) ilde{O}(\sqrt{dT}) i l d e O ( d T ) and logarithmic regret under positive suboptimality gap. The paper develops a Hoeffding inequality for Markov chains and applies it to bandit problems.
problem Developing a Hoeffding inequality for Markov chains and applying it to bandit problems.
method Developed a Hoeffding inequality for the partial sums of an irreducible Markov chain on a finite state space.
result Demonstrated the inequality's effectiveness in identifying approximately best Markovian arms and minimizing regret in Markovian bandits.
I analyse the frequentist regret of the famous Gittins index strategy for multi-armed bandits with Gaussian noise and a finite horizon. Remarkably it turns out that this approach leads to finite-time regret guarantees comparable to those available for the popular UCB algorithm. Along the way I derive finite-time bounds…
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.
A new algorithm reduces suboptimal arm selection in correlated bandits.
problem Structured bandits with correlated rewards.
method Confidence-based phased algorithm.
result Regret is uniformly bounded in certain structures.
Study optimal adaptive allocation for multi-armed bandits with Markovian rewards.
problem Optimal adaptive allocation for multi-armed bandits with Markovian rewards.
method Round-robin Kullback-Leibler upper confidence bounds for optimal adaptive allocation.
result Logarithmic dependence of regret on time horizon, asymptotically optimal.
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.
Study best arm identification in restless Markov multi-armed bandits with state-dependent transitions.
problem Identify the best arm in a multi-armed bandit with time-varying states.
method Propose a sequential policy to select arms without knowing their exact TPMs.
result Upper and lower bounds on expected time to find the best arm match in a special case.
Optimal algorithm found for collaborative learning in bandits with optimal regret bounds.
problem Minimizing regret in collaborative multi-agent bandit problems.
method Proposed an algorithm with optimal regret bounds for collaborative multi-agent multi-armed bandit model.
result First algorithm with order optimal regret bounds for collaborative bandit model.
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.
Algorithm learns similarities to optimize bandit decisions in unknown metric space.
problem Optimizing decisions in unknown metric space with nonparametric reward functions.
method Data-driven similarities for adaptive partitioning of context-arm space.
result Regret bounds highlight algorithm's dependence on reward functions' local geometry.
Study quantile multi-armed bandits for identifying the best arm with a specified quantile level.
problem Identifying the arm with the highest quantile in multi-armed bandits with private rewards.
method Proposed a (non-private) and differentially private successive elimination algorithms for best-arm identification.
result The proposed algorithms are essentially optimal for quantile bandit problems, with finite sample complexity even for distributions with infinite support-size.
Paper tackles identifying an odd arm in a multi-armed bandit with restless Markov processes and trembling hand.
problem Identifying an odd arm in a multi-armed bandit with restless Markov processes and trembling hand.
method Derive asymptotic lower bound on expected time to identify the odd arm, stitch together parameterised solutions to MDPs.
result First known asymptotic lower bound on expected time to identify the odd arm, with vanishing error probability.
We study a multiplayer stochastic multi-armed bandit problem in which 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 the challenging heterogeneous setting, in which different arms may have different means for differe…
New method tracks shifts in infinite-armed bandits without prior knowledge.
problem Tracking shifts in non-stationary infinite-armed bandits.
method Blackbox conversion of finite-armed MAB to infinite-armed non-stationary, randomized elimination.
result First parameter-free optimal regret bounds for all reservoir regularity regimes.
Paper tackles anomaly detection in restless Markov arms with unknown TPMs.
problem Detecting an anomalous arm in a multi-armed bandit with unknown transition probability matrices.
method Developed a policy based on the principle of certainty equivalence, achieving the lower bound arbitrarily closely under specific assumptions.
result Achieved the lower bound on expected time required to find the odd arm index, demonstrating the policy's effectiveness.
Develops a framework for clustering and distribution matching with bandit feedback.
problem Clustering and distribution matching problems with limited feedback.
method General framework using K K K -armed bandit model, Track-and-Stop method, and Frank--Wolfe algorithm. result Average number of arm pulls matches lower bound, with asymptotic convergence to fundamental limit.
Policy gradient algorithm with variable learning rates achieves near-optimal performance in multi-arm bandit problems.
problem Optimizing a policy gradient algorithm for multi-arm bandit problems with variable learning rates.
method Applied Foster-Lyapunov techniques to analyze a Markov chain formed by the state of the algorithm.
result The policy gradient algorithm converges to the optimal arm with logarithmic or poly-logarithmic regret.
This paper analyzes the multi-armed bandit model using path-integral methods.
problem Understanding the stochastic dynamics and optimal strategies in multi-armed bandit problems.
method Path-integral analysis of statistical physics.
result Emergence of multimodal regret distribution with large regrets from exploitation of sub-optimal arms.
Optimal best arm identification for multi-objective bandits with fixed error probability.
problem Identifying the best arm for each of multiple objectives with fixed confidence.
method Surrogate proportions to sample arms at each time step, eliminating max-min optimisation.
result Asymptotically optimal algorithm for multi-objective best arm identification.
New bounds derived for KG algorithm's performance in finite time.
problem Best arm identification problem in multi-armed bandit.
method Theoretical analysis of finite-time performance, deriving bounds for sample allocation, error probability, and regret.
result Upper and lower bounds for the probability of error and simple regret of the KG algorithm.
We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investigated in (Cope 2009, Yu 2011). The set of arms is either discrete, in which case arms correspond to the vertices of a finite graph whose stru…
Study on bandit problem with fixed number of arm types, achieving optimal regret bounds.
problem Stochastic multi-armed bandit problem with a fixed number of arm types.
method Proposes algorithms achieving optimal regret bounds for the problem.
result Achieves $\mathcal{O}\left( \log n
ight)$ instance-dependent regret and $ ilde{\mathcal{O}}\left( \sqrt{n}
ight)$ instance-independent regret.
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.
New algorithm identifies best arm in non-stationary linear bandits with improved complexity.
problem Best arm identification in non-stationary linear bandits with adversarial parameters.
method Proposed Adjacent-optimal design and e x t s f A d j a c e n t − B A I extsf{Adjacent-BAI} e x t s f A d j a ce n t − B A I algorithm. result Error probability matches arm-set-dependent lower bound up to constants.
Paper tackles best mixed arm identification with cost constraints in bandit models.
problem Finding the best mixed arm with cost constraints in a stochastic bandit model.
method Proposes SFSR algorithm combining successive reject and score-function-based rejection criteria.
result Upper and lower bounds on mis-identification probability show exponential decay with budget.
Opt-BBAI identifies the best arm with minimal batches and pulls, optimizing both sample and batch complexity.
problem Batched best arm identification (BBAI) problem, aiming to minimize policy switches and resource usage.
method Proposed Opt-BBAI algorithm, achieving near-optimal sample and batch complexity in non-asymptotic settings.
result First algorithm to achieve near-optimal sample and batch complexity in non-asymptotic settings.
Optimal algorithm identifies best arm for risk measures in heavy-tailed distributions.
problem Identifying the arm with smallest CVaR, VaR, or weighted sum of CVaR and mean from heavy-tailed distributions.
method Multi-armed bandit best-arm identification framework, solving non-convex optimization problem.
result Optimal δ-correct algorithm with matching lower bound on expected samples.
Optimal top-2 method improves best arm identification with reduced error.
problem Identifying the arm with the highest mean in a set of arms.
method A novel top-2 algorithm that pulls the empirical best arm with probability β and the challenger arm otherwise.
result The proposed algorithm matches the information theoretic lower bound on sample complexity as δ approaches 0.
The target of X \mathcal{X} X -armed bandit problem is to find the global maximum of an unknown stochastic function f f f , given a finite budget of n n n evaluations. Recently, X \mathcal{X} X -armed bandits have been widely used in many situations. Many of these applications need to deal with large-scale data sets. To deal with…
Optimal strategy proposed for maximizing cumulative reward in continuum-armed bandits.
problem Maximizing cumulative reward in a scenario with limited resources and unknown stochastic rewards.
method Proposed an optimal strategy for a nonparametric setting with side information on actions.
result Optimal regret scales as \(O(T^{1/3})\) up to poly-logarithmic factors when \(T\) is proportional to \(N\).
We consider a finite-armed structured bandit problem in which mean rewards of different arms are known functions of a common hidden parameter θ ∗ θ^* θ ∗ . Since we do not place any restrictions of these functions, the problem setting subsumes several previously studied frameworks that assume linear or invertible reward funct…
A new algorithm for fair decision-making in bandit problems with biased feedback.
problem Fair allocation of resources across sensitive groups in bandit problems with biased feedback.
method Proposes a novel algorithm that learns a societal bias term to mitigate unfairness in multi-armed bandit problems.
result The proposed algorithm achieves a theoretical bound on regret and demonstrates fairness in synthetic and real-world data.