DETC algorithm achieves asymptotic optimality in multi-armed bandit problems.
problem Multi-armed bandit problem with subgaussian rewards.
method DETC algorithm with two exploration and exploitation phases.
result DETC achieves asymptotically optimal regret bound.
New algorithm tackles high-dimensional contextual bandits without sparsity.
problem High-dimensional linear contextual bandit problem with large feature space.
method Proposes explore-then-commit (EtC) and adaptive explore-then-commit (AEtC) algorithms.
result Derives optimal rate for ETC algorithm and shows adaptive AEtC achieves it.
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…
New algorithm tackles nonstationary linear bandits with latent dynamics.
problem Nonstationary bandit problem with latent states and unknown dynamics.
method Explore-then-commit algorithm with exploration and commitment phases.
result Achieves i l d e O ( T 2 / 3 ) ilde{\mathcal{O}}(T^{2/3}) i l d e O ( T 2/3 ) regret. New algorithm for decentralized matching markets without prior preference rankings.
problem Decentralized two-sided matching markets without known preference rankings.
method Epoch-based CA-ETC algorithm for decentralized matching markets.
result Achieves player optimal expected regret of O(T_0 (K log T / T_0 Δ^2)^(1/γ) + T_0 (T / T_0)^γ).
New framework tackles submodular welfare with multi-agent combinatorial bandits.
problem Maximizing total welfare among agents with shared constraints and submodular utilities under bandit feedback.
method Proposes an explore-then-commit strategy with randomized assignments for multi-agent combinatorial bandits.
result Achieves i l d e O ( T 2 / 3 ) ilde{\mathcal{O}}(T^{2/3}) i l d e O ( T 2/3 ) regret, first for partition-based submodular welfare problem under bandit feedback. New bounds for high-dimensional sparse linear bandits, balancing information and regret.
problem Stochastic linear bandits with high-dimensional sparse features.
method Derivation of minimax regret lower and upper bounds for explore-then-commit algorithm.
result Optimal rate of Θ ( n 2 / 3 ) Θ(n^{2/3}) Θ ( n 2/3 ) for data-poor regime, complemented by O ( n ) O(\sqrt{n}) O ( n ) under signal magnitude assumption. The paper minimizes Borda regret in dueling bandits models.
problem Minimizing Borda regret in dueling bandits models.
method Proposes explore-then-commit and EXP3-type algorithms for stochastic and adversarial settings respectively.
result Achieves nearly matching regret upper bounds of O ( d 2 / 3 T 2 / 3 ) O(d^{2/3} T^{2/3}) O ( d 2/3 T 2/3 ) for both settings. We study the problem of regret minimization in partially observable linear quadratic control systems when the model dynamics are unknown a priori. We propose ExpCommit, an explore-then-commit algorithm that learns the model Markov parameters and then follows the principle of optimism in the face of uncertainty to desig…
Paper proposes DG-ETC for online submodular maximization with stochastic bandit feedback.
problem Online unconstrained submodular maximization with stochastic bandit feedback.
method Double-Greedy - Explore-then-Commit (DG-ETC) approach.
result DG-ETC achieves logarithmic regret O ( d log ( d T ) ) O(d\log(dT)) O ( d log ( d T )) for 1 / 2 1/2 1/2 -approximate pseudo-regret. Study local exploration on dynamic graphs with time-varying edges.
problem Learning optimal actions in a network with changing connections.
method Local explore-then-commit algorithms under a structural condition ensuring intrinsic walk stability.
result Sublinear expected regret for reward-aware strategies.
Algorithm achieves optimal pricing with minimal exploration for dynamic markets.
problem Optimal pricing in dynamic markets with contextual information.
method Localized exploration-then-commit (LetC) algorithm with pure exploration, refinement, and exploitation stages.
result Achieves minimax optimal, dimension-free regret bound.
GL-LowPopArt improves minimax-optimal estimation for trace regression.
problem Minimizing estimation error in generalized low-rank trace regression.
method Two-stage approach: nuclear norm regularization followed by matrix Catoni estimation.
result Achieves instance-wise optimal error bounds up to condition number.
New algorithm for combinatorial bandit problems reduces regret.
problem Optimal selection of sets of arms in bandit problems.
method SGB algorithm with optimized exploration of unselected arms.
result Achieves ( 1 − 1 / e ) (1-1/e) ( 1 − 1/ e ) -regret bound of O ( n 1 3 k 2 3 T 2 3 log ( T ) 2 3 ) \mathcal{O}(n^{\frac{1}{3}} k^{\frac{2}{3}} T^{\frac{2}{3}} \log(T)^{\frac{2}{3}}) O ( n 3 1 k 3 2 T 3 2 log ( T ) 3 2 ) . Paper introduces a bandit-learning method for multifidelity approximations.
problem Efficiently using data of varying fidelities in scientific computation.
method Formulates multifidelity approximation as a modified stochastic bandit problem and proposes AETC algorithm.
result Established optimality of AETC algorithm for multifidelity approximation.
Paper proposes efficient online estimation of causal effects by deciding which data sources to query.
problem Data fusion problems with multiple data sources capturing distinct subsets of variables.
method Online moment selection (OMS) framework, balancing exploration and exploitation.
result OMS algorithms achieve zero asymptotic regret for estimating average treatment effects.
A new algorithm selects models for contextual bandits, reducing regret.
problem Model selection for stochastic contextual bandits under realizability assumption.
method Adaptive Contextual Bandit (ACB) algorithm, successive refinement phases.
result ACB algorithm achieves similar regret bound to known algorithms, with a model selection cost.
New approach limits regret in non-stationary bandits.
problem Understanding worst case regret in time-varying bandits.
method Belief inertia argument to resist new evidence after changes.
result Linear worst case regret for classical and restarting algorithms.
Optimal online data collection for semiparametric inference reduces regret.
problem Sequential data collection decisions for efficient estimation under budget constraints.
method Online Moment Selection framework; Explore-then-Commit and Explore-then-Greedy policies.
result Online data collection policies achieve zero regret relative to an oracle policy.
Efficient algorithms for second-price auctions with action-dependent censoring.
problem Sequential bidding strategies for repeated auctions with incomplete information.
method Proposed novel UCB-like algorithms for second-price auctions in a stochastic setting.
result Significant improvement in worst-case regret, especially for low item values.
New method proves fast regret bounds for online RLHF with generalized preferences.
problem Minimizing max-regret in online RLHF with general preferences and bandit feedback.
method Adopted Generalized Bilinear Preference Model (GBPM) to investigate polylogarithmic regret guarantees.
result Proved polylogarithmic regret bounds for Greedy Sampling and Explore-Then-Commit policies under GBPM.
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.
New MAB model incentivizes user arm-pulling with self-reinforcing preferences.
problem Balancing exploration and exploitation in recommender systems with incentivized user preferences.
method Proposes a new MAB model with random arm selection and two policies: At-Least- n n n Explore-Then-Commit and UCB-List. result Achieves O ( l o g T ) O(log T) O ( l o g T ) expected regret and O ( l o g T ) O(log T) O ( l o g T ) expected payment over a time horizon T T T . New RLHF algorithm identifies optimal policies from human feedback without explicit reward inference.
problem Training large language models with human feedback without reward inference.
method Model-free RLHF algorithm B S A D \mathsf{BSAD} BSAD that identifies optimal policies directly from human preference. result Provable, instance-dependent sample complexity i l d e O ( c M S A 3 H 3 M log 1 δ ) ilde{\mathcal{O}}(c_{\mathcal{M}}SA^3H^3M\log\frac{1}δ) i l d e O ( c M S A 3 H 3 M log δ 1 ) . New approach to multi-armed bandit problem aims to maximize highest total reward.
problem Traditional multi-armed bandit problem objective of maximizing total reward is not suitable in certain applications.
method Adaptive explore-then-commit policy with confidence bounds and adaptive stopping criterion.
result Achieves asymptotic and worst-case regret bounds for the new objective.
Algorithm learns interference network and optimizes treatment allocation for unknown network effects.
problem Adaptive experimentation under unknown network interference.
method Thompson sampling algorithm with Gibbs sampler for joint learning of interference network and treatment allocation.
result Proves a Bayesian regret bound and achieves sublinear regret in real-world applications.
New method for online low-rank matrix completion with improved regret.
problem Designing an efficient algorithm for online recommendation systems with low regret.
method Explore-then-commit (ETC) approach and iterative user clustering (OCTAL) for rank-1 setting.
result Nearly optimal regret bounds for online low-rank matrix completion.
This work tackles representation learning for RL in low-rank MDPs, improving sample efficiency.
problem How to learn a compact representation for RL in low-rank MDPs efficiently.
method Proposes REP-UCB for online RL and develops an algorithm for offline RL under partial coverage.
result Significantly improved sample complexity for online RL and competitive performance for offline RL.
The paper studies how to allocate human validation in AI-assisted tasks to minimize errors.
problem Heterogeneous reliability of AI-generated signals across tasks, products, and customer segments.
method Tuned prediction-powered inference, upper confidence bounds policy, Neyman square-root rule.
result The proposed policy outperforms uniform and epsilon-greedy allocation, closing most of the gap to the oracle when reliability is heterogeneous.