UCRL-WVTR tackles long-term reinforcement learning with general approximations, achieving horizon-free and instance-dependent regret bounds.
problem Long-term reinforcement learning with general function approximations.
method UCRL-WVTR proposes a novel algorithm, UCRL-WVTR, with weighted value-targeted regression and a high-order moment estimator.
result Achieves horizon-free and instance-dependent regret bounds matching minimax lower bounds up to logarithmic factors.
New algorithms improve contextual bandit performance by adapting to problem difficulty.
problem Improving contextual bandit performance on problems with varying difficulty.
method Introducing complexity measures and oracle-efficient algorithms.
result Achieves optimal instance-dependent regret bounds for rich policy classes.
New reinforcement learning algorithm achieves instance-optimal sample complexity.
problem Achieving low regret and identifying optimal policies in reinforcement learning.
method A novel planning-based algorithm that explicitly accounts for state visitation distributions.
result The proposed algorithm attains nearly minimax optimal sample complexity, improving over worst-case bounds.
No communication allows optimal instance-dependent regret guarantees in multi-player bandits.
problem Achieving optimal instance-dependent regret in multi-player multi-armed bandits without communication.
method Characterization of Pareto optimal trade-offs and development of an algorithm.
result Achieving optimal instance-dependent regret requires strict sub-optimality in other regimes.
New algorithm tackles heavy-tailed rewards in RL with instance-dependent regret bounds.
problem Efficient algorithms for RL with heavy-tailed rewards in large state-action spaces.
method Design of \textsc{Heavy-OFUL} for heavy-tailed linear bandits and \textsc{Heavy-LSVI-UCB} for RL with linear function approximation.
result First instance-dependent regret bounds for heavy-tailed rewards in RL with linear function approximation.
Algorithm reduces regret in multi-player bandits with unknown collision rewards.
problem Reducing regret in multi-player multi-armed bandits with unknown collision rewards.
method Proposes an algorithm that combines a modified successive elimination strategy with a communication protocol to estimate suboptimality gaps and coordinate among players.
result Achieves logarithmic regret for the problem when collision reward is unknown.
Two algorithms tackle heavy-tailed rewards in reinforcement learning with linear function approximation.
problem Online sequential decision-making with heavy-tailed rewards.
method AdaOFUL and VARA algorithms for linear stochastic bandits and MDPs, using modified adaptive Huber regression.
result Achieved state-of-the-art and variance-aware regret bounds for heavy-tailed rewards.
Unified framework for distributional regret in bandits and reinforcement learning.
problem Characterizing the distribution of regret in multi-armed bandits and reinforcement learning.
method Unified framework with a UCBVI-style algorithm and distributional regret bounds.
result Distributional regret bounds with optimal trade-offs between expected and distributional regret.
Papers learn from data to make decisions without interacting, improving on previous methods.
problem Achieving optimal decision-making from offline data with non-linear function approximation.
method Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI) with three innovative components.
result Achieves minimax optimal instance-dependent regret for non-linear function approximation.
New CTRL algorithm adapts to varying problem difficulty.
problem Adapting to varying levels of problem difficulty in CTRL.
method MLE with a general function approximator, estimating state marginal density.
result Regret bound scales with reward variance and measurement resolution, independent of measurement strategy.
RL-LOW algorithm achieves exponential simple regret in offline RLHF with pairwise comparisons.
problem Offline reinforcement learning from human feedback with pairwise comparisons.
method Proposes RL-LOW algorithm to minimize simple regret with exponential convergence.
result Achieves an exponential form of simple regret of \(\exp ( - Ω(n/H) )\).
New algorithm reduces regret by allowing free exploration in multi-armed bandits.
problem Designing an adaptive policy to minimize regret with a free exploration budget.
method Introduced ( α , β ) (α,β) ( α , β ) -probably saving policies and a two-phase algorithm UFE-KLUCB-H. result UFE-KLUCB-H accumulates strictly less regret than non-free exploration policies.
New algorithm reduces regret for kernelized bandits by adapting to specific problem instances.
problem Efficiently learning the optimizer of an unknown function in RKHS with noisy oracle.
method Instance-dependent regret analysis and a new minimax near-optimal algorithm.
result New algorithm achieves better performance on specific problem instances.
Optimizes regret distribution in stochastic bandits for risk balance.
problem Balancing regret expectation and tail risk in stochastic bandits.
method Characterizes optimal regret tail probability for any threshold, proposes new policies.
result Discovers an intrinsic gap in optimal tail rate based on time horizon uncertainty.
Study contextual online pricing with biased offline data, achieving optimal regret bounds.
problem Contextual online pricing with biased offline data.
method Identify δ 2 δ^2 δ 2 to measure data bias, use OFU policy and robust variant for unknown bias. result Achieve minimax-optimal regret bounds for contextual pricing.
Algorithm tackles adaptive discretization in adversarial Lipschitz bandits for dynamic pricing and auctions.
problem Adaptive discretization in adversarial Lipschitz bandits.
method Adversarial Zooming algorithm for adaptive discretization.
result First algorithm for adversarial Lipschitz bandits with instance-dependent regret bounds.
ERTS uses Thompson sampling for Gaussian entropic risk bandits, achieving regret bounds.
problem Risk in decision making complicates reward maximization in MAB problems.
method ERTS (Entropic Risk Thompson Sampling) using Thompson sampling with an entropic risk measure.
result Regret bounds for ERTS under entropic risk measure provided.
Improved Thompson Sampling using fractional posteriors achieves better regret bounds.
problem Optimizing regret in stochastic multi-armed bandit problems.
method Using α \alpha α -posterior distributions, derived frequentist regret bounds. result Instance-dependent and instance-independent regret bounds established.
New algorithm reduces regret and constraint violation in online convex optimization with complex constraints.
problem Online convex optimization with multiple functional constraints and a simple constraint set.
method Instance-dependent bound using online primal-dual mirror-prox algorithm in general normed spaces.
result Achieves an O(√V*(T)) regret and O(1) constraint violation, improving over previous works.
Logarithmic regret for continuous-time reinforcement learning.
problem Continuous-time Markov decision processes with unknown transition probabilities and holding times.
method Upper confidence reinforcement learning, mean holding time estimation, stochastic comparison of point processes.
result Logarithmic regret bound achieved in finite time.
New algorithm reduces contextual bandit identification to argmax calls.
problem Best-arm identification in stochastic contextual bandits.
method Instance-optimal PAC algorithm using argmax oracle calls.
result First instance-dependent PAC sample complexity for contextual bandits.
Algorithm extsc{Pedel} learns near-optimal policies efficiently on specific problems.
problem Learning near-optimal policies in linear MDPs with minimal samples.
method Online experiment design to focus exploration on relevant directions.
result Achieves instance-dependent complexity, outperforming minimax-optimal algorithms.
Improved adaptive rates for Lipschitz bandit problem.
problem Sequentially maximize an unknown Lipschitz function with noisy evaluations.
method Characterizes regret through integrals of suboptimality gaps over level sets, adapting to local growth.
result Improved adaptive rates strictly improving over classical zooming 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.
The paper tackles best arm identification with minimal regret in experiments.
problem Identifying the best arm with minimal regret in experiments.
method Information-theoretic techniques and Double KL-UCB algorithm.
result Achieves asymptotic optimality in identifying the best arm with minimal regret.
Flexible algorithms for maximizing rewards in structured bandits.
problem Reward maximization in structured stochastic multi-armed bandit problems.
method Asymptotically optimal algorithms using iterative saddle-point solvers.
result Achieves optimal performance with minimal computational burden.
New algorithms minimize simple and cumulative regret in contextual bandits.
problem Minimizing simple and cumulative regret in contextual bandit settings.
method Proposed new algorithms using conformal arm sets (CASs).
result Near-optimal minimax guarantees for simple regret and state-of-the-art guarantees for cumulative regret.
Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for lo…
Adaptive algorithms minimize regret in matching markets with contextual arm preferences.
problem Minimizing regret in matching markets with context-dependent player utilities.
method Developed adaptive algorithms for stochastic and adversarial contexts, providing upper and lower bounds.
result Achieved sublinear regret bounds for both stochastic and adversarial contexts.
Paper tackles robust batched bandits for heavy-tailed rewards.
problem Clinical trials and other applications with heavy-tailed rewards.
method Proposes robust batched bandit algorithms for heavy-tailed rewards in finite-arm and Lipschitz-continuous settings.
result Heavier-tailed rewards require fewer batches for near-optimal regret in the instance-independent regime and Lipschitz setting.
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.
We introduce efficient algorithms which achieve nearly optimal regrets for the problem of stochastic online shortest path routing with end-to-end feedback. The setting is a natural application of the combinatorial stochastic bandits problem, a special case of the linear stochastic bandits problem. We show how the diffi…
We consider combinatorial online learning with subset choices when only relative feedback information from subsets is available, instead of bandit or semi-bandit feedback which is absolute. Specifically, we study two regret minimisation problems over subsets of a finite ground set [ n ] [n] [ n ] , with subset-wise relative prefe…
Optimizes arm selection with side information in Gaussian bandits.
problem Optimizing arm selection with side information in Gaussian bandits.
method Constructs an LP-based asymptotic instance-dependent lower bound on the regret and develops the first known asymptotically optimal algorithm.
result First known asymptotically optimal algorithm for Gaussian bandits with side information.
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.
New study on regret lower bounds for multi-agent multi-armed bandit problems.
problem Understanding the limits of performance in multi-agent multi-armed bandit problems.
method Comprehensive study on different settings, establishing tight lower bounds.
result First comprehensive study on regret lower bounds across various settings.
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 algorithm CROP achieves asymptotic optimality with bounded regret.
problem Optimistic algorithms fail to achieve asymptotic instance-dependent regret optimality.
method CRush Optimism with Pessimism (CROP) algorithm that eliminates optimistic hypotheses.
result CROP achieves constant-factor asymptotic optimality and bounded regret.
COF algorithm minimizes cost in multi-armed bandits with known costs and reward constraints.
problem Minimizing cost while meeting a minimum reward requirement in uncertain environments.
method COF algorithm that intelligently combines samples from all arms to gauge feasibility and minimize cost.
result COF achieves instance-dependent upper bounds on cumulative cost and quality regret.
Thompson sampling for multi-armed bandit problems is known to enjoy favorable performance in both theory and practice. However, it suffers from a significant limitation computationally, arising from the need for samples from posterior distributions at every iteration. We propose two Markov Chain Monte Carlo (MCMC) meth…
The paper achieves nearly optimal regret bounds for contextual multinomial logit bandits.
problem The contextual multinomial logit (MNL) bandit problem with varying rewards.
method Established lower bounds and proposed OFU-MNL+ algorithm with matching upper bounds.
result Achieved minimax optimal regret bounds for both uniform and non-uniform reward settings.
Paper tackles instance-dependent label noise by approximating it with part-dependent noise.
problem Learning with instance-dependent label noise is challenging.
method Approximate instance-dependent label noise with part-dependent noise. Use transition matrices for parts to model noise.
result Method outperforms state-of-the-art approaches for instance-dependent label noise.
Improved neural active learning algorithms reduce regret and improve performance.
problem Improving performance and reducing regret in neural active learning for non-parametric streaming data.
method Introducing two new regret metrics and leveraging NNs for both exploitation and exploration. The algorithm uses tailored query decision-makers and full feedback.
result Achieved an instance-dependent regret upper bound improving by a multiplicative factor of O ( log T ) O(\log T) O ( log T ) and removing the curse of dimensionality. E 4 ^4 4 algorithm optimizes batched linear bandits with minimal regret and batches.
problem Optimizing batched linear bandits for minimal regret.
method Explore-Estimate-Eliminate-Exploit framework with optimal exploration rate.
result Achieves minimax and asymptotic optimality in regret and batch complexity.
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 ) . A new SSL method uses instance-dependent thresholds to improve accuracy.
problem Improving semi-supervised learning by better selecting confident unlabeled instances.
method Proposes instance-dependent thresholds that vary based on the ambiguity and error rates of pseudo-labels for each unlabeled instance.
result Demonstrates that instance-dependent thresholds provide a probabilistic guarantee for correct pseudo-labels.
BeGIN benchmarks GNNs for instance-dependent label noise in graphs.
problem Instance-dependent label noise in graph data.
method BeGIN introduces a benchmark with various noise types and evaluates noise-handling strategies across GNN architectures.
result Challenges of instance-dependent noise, especially LLM-based corruption, and the importance of node-specific parameterization.
Algorithm aggregates rewards from multiple players to learn related tasks in online bandit learning.
problem Learning related but slightly different tasks in an online setting with heterogeneous feedback.
method RobustAgg ( ε ) (ε) ( ε ) algorithm that aggregates rewards from different players. result Achieves instance-dependent regret guarantees and nearly matching lower bounds.