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.
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. 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.
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. 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.
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.
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.
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. New algorithms use offline data to improve online decision-making with latent states.
problem Accelerating online sequential decision-making with latent states in offline data.
method Design end-to-end latent bandit algorithms for linear latent contextual bandits, learning latent subspace offline and using it online.
result Proves minimax optimal regret guarantees for online algorithms and practical efficiency.
Paper proposes efficient offline neural bandit method.
problem Offline policy learning with neural networks.
method Provable efficient offline contextual bandit with neural network function approximation.
result Method provably generalizes over unseen contexts.
Combines offline and online learning for identifying the best arm in bandits.
problem Identifying the best arm in stochastic bandits with offline data.
method Lower bound analysis and algorithm development for optimal best-arm identification.
result Developed algorithms matching lower bound on sample complexity for small δ.
Algorithm reduces online regret by leveraging offline data in linear bandits.
problem Online regret minimization in linear bandits with offline data.
method OOPE algorithm using extended D-optimal design.
result Substantial reduction in online regret compared to prior work.
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.
New method optimizes offline linear bandits using different confidence sets.
problem Optimizing offline learning for linear contextual bandits.
method Introduces a family of pessimistic learning rules based on ℓ p \ell_p ℓ p confidence sets. result The π ^ ∞ \hatπ_\infty π ^ ∞ rule achieves minimax performance and strictly dominates other predictors. A new method combines online and offline learning to tackle contextual bandits with missing action support.
problem Learning optimal policies with logged data when the logging policy has deficient support.
method Hybrid approach using online exploration to exploit supported actions and offline learning to avoid unnecessary explorations.
result Determines an optimal policy with theoretical guarantees using minimal online explorations.
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 algorithm minimizes Bayesian regret in offline linear bandits.
problem Minimizing Bayesian regret in offline linear bandits.
method Proposes a new algorithm that directly minimizes upper bounds on Bayesian regret using conic optimization.
result Upper bounds are tight and guarantee superior performance compared to LCB.
Adapts to misspecification in contextual bandits using offline regression.
problem Unexpected regret due to misspecified reward models.
method Adapts to misspecification by reverting to a safe policy when necessary.
result Regret guarantees degrade gracefully with misspecification level.
The paper tackles bandit problems with biased offline data by using causal methods.
problem Improving bandit algorithms with biased offline data that includes confounding and selection biases.
method Formalizes the problem from a causal perspective, categorizes biases, and derives robust bounds for each arm.
result Causal bounds can guide the bandit agent to learn a nearly-optimal decision policy and consistently reduce asymptotic regret.
Study minimax-optimal rates for offline decision-making with function approximation.
problem Statistical complexity of offline decision-making with function approximation.
method Near minimax-optimal rates for stochastic contextual bandits and Markov decision processes, using pseudo-dimension and behavior policy.
result Established performance limits and new characterization of behavior policy.
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.
Combines offline causal inference and online bandit learning for better decision-making.
problem Making adaptive decisions using both logged and streaming data to avoid user harm.
method Unified offline causal inference and online learning algorithms, deriving bounds on decision accuracy.
result First upper regret bound for forest-based online bandit algorithms.
Contextual bandit algorithms have become popular for online recommendation systems such as Digg, Yahoo! Buzz, and news recommendation in general. \emph{Offline} evaluation of the effectiveness of new algorithms in these applications is critical for protecting online user experiences but very challenging due to their "p…
Overparameterized models generalize well in offline contextual bandits, but policy-based algorithms struggle.
problem The performance gap between value-based and policy-based algorithms in offline contextual bandits with overparameterized models.
method Analysis of action-stability in objectives and formal proofs of regret bounds.
result The performance gap is due to action-stability of objectives, with value-based objectives being stable and policy-based objectives unstable.
Paper analyzes sample complexity for offline f f f -divergence-regularized contextual bandits.
problem Lack of tight analyses for sample complexity in offline reinforcement learning.
method Novel pessimism-based analysis for reverse KL divergence, establishing i l d e O ( ε − 1 ) ilde{O}(ε^{-1}) i l d e O ( ε − 1 ) sample complexity. result Achieves i l d e O ( ε − 1 ) ilde{O}(ε^{-1}) i l d e O ( ε − 1 ) sample complexity for reverse KL divergence, surpassing existing bounds. 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.
Transforms offline greedy algorithms to online algorithms for combinatorial problems.
problem Online decision-making in time-varying combinatorial environments.
method General framework using Blackwell approachability and Bandit Blackwell approachability.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret in full information setting and O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) regret in bandit setting. A new algorithm CAP learns optimal policies from observational data with confounding bias and missing observations.
problem Offline contextual bandit with confounding bias and missing observations.
method CAP policy learning, forming reward function as solution of integral equation system, building confidence set, and greedily taking action with pessimism.
result Developed an upper bound to the suboptimality of CAP for the offline contextual bandit problem.
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. 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.
Survey and compare PAC-Bayes bounds for bandit problems.
problem Designing and evaluating bandit algorithms with strong performance guarantees.
method PAC-Bayes bounds applied to bandit problems.
result PAC-Bayes bounds useful for offline bandit algorithms, but loose for online algorithms.
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. Unified framework for risk-aware policy learning in contextual bandits.
problem Optimizing decision rules in high-stakes domains with adverse outcomes.
method Distributional framework for Lipschitz-continuous risk functionals, with novel empirical concentration inequalities.
result Data-dependent suboptimality bounds with an i l d e O ( 1 / n ) ilde{\mathcal{O}}(1/\sqrt{n}) i l d e O ( 1/ n ) rate, matching risk-neutral offline policy optimization. New algorithms tackle latent bandit problems with lower regret.
problem Learning optimal actions in a latent state setting.
method General algorithms based on UCBs and Thompson sampling, aware of model uncertainty.
result Our methods have lower regret than classic bandit policies when latent states are fewer than actions.
Paper refines PAC-Bayes bounds for bandit problems.
problem Improving probabilistic bounds for off-policy learning.
method Optimizes PAC-Bayesian bounds using a new parameter optimization approach.
result Provides two parameter-free PAC-Bayes bounds that nearly match optimal rates.
New approach for off-policy learning in contextual bandits with performance guarantees.
problem Improving performance of logging policies in contextual bandits.
method PAC-Bayesian analysis of policy mixtures, providing tighter generalization bounds and tractable optimization algorithms.
result Proved tighter generalization bounds and demonstrated effectiveness in practical scenarios.
This paper sets communication complexity bounds for distributed RL.
problem Establishing minimum communication requirements for distributed RL.
method Information-theoretic lower bounds and algorithm development.
result Developed algorithms achieving optimal risk up to logarithmic factors.
Improved guarantees for misspecified kernelized bandit optimization.
problem Misspecification in kernelized bandit optimization.
method Localization and domain splitting techniques.
result Logarithmic or polylogarithmic growth of misspecification amplification.
Efficiently identifies good policies by choosing contexts for human feedback.
problem Efficiently identifying good policies in applications with high feedback costs.
method Introduces offline contextual dueling bandit setting and an upper-confidence-bound style algorithm.
result Proves a regret bound and shows superior performance over uniformly sampled contexts.
Meta-KeL learns kernels from offline data to improve sequential decision-making.
problem Adaptive confidence sets for prediction functions in sequential decision-making tasks.
method Meta-KeL: meta-learning a kernel from offline data; structured sparsity estimator for unknown kernel combinations.
result Valid confidence sets that become as tight as those given the true unknown kernel with increasing offline data.
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. What is the most statistically efficient way to do off-policy evaluation and optimization with batch data from bandit feedback? For log data generated by contextual bandit algorithms, we consider offline estimators for the expected reward from a counterfactual policy. Our estimators are shown to have lowest variance in…
The paper tackles personalized policy learning from diverse data sources in a federated setting.
problem Learning personalized decision policies from observational bandit feedback across multiple heterogeneous data sources.
method Introduces a novel regret analysis for distinguishing global and local regret, and presents a federated policy learning algorithm using local policies trained with doubly robust offline policy evaluation strategies.
result Establishes finite-sample upper bounds on global and local regret, characterizing them by source heterogeneity and distribution shift.
Unified meta algorithms estimate various distribution functionals in infinite-armed bandits.
problem Estimating various distribution functionals in infinite-armed bandits.
method Unified meta algorithms for offline and online settings, achieving optimal sample complexities.
result Online estimation offers significant advantage for certain distribution functionals.
Deep Bayesian Bandits improve personalized ads by balancing exploration and exploitation.
problem Recommender systems favor items already engaged by users, causing new campaigns to remain unexplored.
method Formulated as a contextual bandit, implemented exploration techniques using posterior distribution and bootstrapped models.
result Demonstrated a positive gain in exploration model in offline simulation and online AB setting.
Paper addresses RLHF alignment challenges with novel algorithms.
problem Challenges in RLHF alignment, especially in strategic exploration.
method Develops a reverse-KL regularized contextual bandit formulation and proposes efficient algorithms with theoretical guarantees.
result Proposed methods significantly outperform existing RLHF algorithms in real-world experiments.
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…
New OPE estimator improves offline policy evaluation for large action spaces.
problem Existing OPE estimators fail with large action spaces, leading to extreme bias and variance.
method Proposes a new estimator using marginalized importance weights and action embeddings.
result Empirical performance improvement enables reliable OPE even with many actions.