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.
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. 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.
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. 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.
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.
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.
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.
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. 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.
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.
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.
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 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.
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. 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.
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…
We study offline data poisoning attacks in contextual bandits, a class of reinforcement learning problems with important applications in online recommendation and adaptive medical treatment, among others. We provide a general attack framework based on convex optimization and show that by slightly manipulating rewards i…
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.
A framework for auto-tuning hyper-parameters in contextual bandit algorithms.
problem Auto-tuning hyper-parameters in real-time for contextual bandit algorithms.
method Proposes a Syndicated Bandits framework to learn multiple hyper-parameters dynamically.
result Achieves optimal regret bounds under certain scenarios and handles multiple contextual bandit algorithms.
We describe MELEE, a meta-learning algorithm for learning a good exploration policy in the interactive contextual bandit setting. Here, an algorithm must take actions based on contexts, and learn based only on a reward signal from the action taken, thereby generating an exploration/exploitation trade-off. MELEE address…
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.
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.
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.
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.
The paper improves off-policy evaluation in contextual bandits using conformal prediction.
problem Quantifying the performance of a target policy using data from a different behavior policy.
method Proposes a novel algorithm based on a PAC-valid conformal prediction framework to construct probably approximately correct prediction intervals.
result Establishes PAC-type bounds on coverage, improving theoretical guarantees.
Spotify improves content mix using contextual bandits.
problem Skewed historical data and varying user preferences across contexts.
method Contextual bandits to dynamically learn optimal content type distribution.
result Improved precision and user engagement with under-represented content types.
Improved off-policy selection and learning in contextual bandits with better guarantees.
problem Selecting or training a reward-maximizing policy using data from a fixed behavior policy.
method A betting-based confidence bound applied to an inverse propensity weight sequence for off-policy selection, and a freezing condition for off-policy learning.
result The proposed methods achieve significantly improved guarantees over prior work, especially in small-data regimes.
A new framework tunes hyperparameters in real-time for contextual bandits.
problem Optimizing hyperparameters for contextual bandits in real-time.
method CDT (Continuous Dynamic Tuning) framework using Zooming TS algorithm.
result Achieves sublinear regret and performs better than existing methods.
Improved algorithm for contextual bandits with reduced regret.
problem Adversarial contextual bandits with i.i.d. contexts.
method Oracle-efficient relaxation with O ( T 2 3 ( K log ( ∣ Π ∣ ) ) 1 3 ) O(T^{\frac{2}{3}}(K\log(|Π|))^{\frac{1}{3}}) O ( T 3 2 ( K log ( ∣Π∣ ) ) 3 1 ) regret bound. result First to improve regret bound and match original bound for stochastic case.
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.
Efficient algorithm for CMDPs reduces to offline density estimation.
problem Offline learning for CMDPs with horizon H.
method Reduction to offline density estimation, layerwise exploration-exploitation tradeoff.
result First efficient and near-optimal reduction from CMDPs to offline density estimation.
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. The paper tackles policy learning in dynamic environments using causal methods.
problem Existing reinforcement learning algorithms assume static mechanisms, but real-world systems often have changing mechanisms.
method The paper introduces multi-environment contextual bandits and policy invariance to handle environmental shifts.
result An optimal invariant policy is guaranteed to generalize across environments under suitable assumptions.
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.
New method improves mHealth user engagement using Thompson sampling for count data.
problem Optimizing mHealth interventions for distal outcomes through proximal context.
method Combines count data models with Thompson sampling for contextual bandits.
result Improves user engagement in mHealth trials compared to existing methods.
CAEL-MIPS learns embeddings to improve MIPS for better OPE in contextual bandits.
problem High variance in IPS weighting for OPE in large action spaces.
method Context-Action Embedding Learning (CAEL) for MIPS to minimize MSE.
result CAEL-MIPS outperforms baselines in MSE for OPE in contextual bandits.
This work compares human feedback methods for reward learning in bandits.
problem Understanding how human feedback affects the performance of reward learning methods.
method Theoretical comparison of human feedback approaches in offline contextual bandits.
result Human bias and uncertainty in feedback modeling impact the theoretical guarantees of reward learning methods.
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.
A new Thompson Sampling framework handles uncertainty by imputing missing data.
problem Handling uncertainty in contextual bandit problems.
method Generative model to impute missing outcomes, fit policy, and select actions.
result Established a state-of-the-art regret bound that depends on generative model quality.
Study batch learning in linear bandits with context, achieving near-optimal performance.
problem Sequential batch learning in linear contextual bandits with finite actions.
method Established regret bounds and provided algorithms for two settings: arbitrary contexts and i.i.d. contexts.
result Regret upper bound nearly matches lower bound, showing polynomial and logarithmic batch requirements.
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…
Improved fast rates for decision making with forward-KL regularization in contextual bandits.
problem Improving fast rates for decision making with forward-KL regularization in contextual bandits.
method Streamlined analysis of forward-KL-regularized offline CBs, exploiting the pessimism principle and convex-analytical pipeline.
result First i l d e O ( ε − 1 ) ilde{O}(ε^{-1}) i l d e O ( ε − 1 ) upper bounds in tabular and general function approximation settings. 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…
Method learns evolving policies in healthcare contexts.
problem Understanding non-stationary behavior in evolving decision-making processes.
method Inverse Contextual Bandits (ICB) approach for learning interpretable representations of non-stationary behavior.
result Demonstrated applicability and accuracy of ICB method in liver transplantation policies.