Study on adaptivity constraints in linear contextual bandits with optimal design.
problem Impact of adaptivity constraints on linear contextual bandits.
method Two models of limited adaptivity: batch learning and rare policy switches. Proposed distributional optimal design.
result Achieves minimax-optimal regret with optimal number of policy switches and batches.
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.
Paper tackles infinite action linear bandits with tight regret bounds.
problem Linear contextual bandit with infinite action sets.
method Proves a regret upper bound of O ( d 2 T log T ) i m e s e x t p o l y ( log log T ) O(\sqrt{d^2T\log T}) imes ext{poly}(\log\log T) O ( d 2 T log T ) im ese x t p o l y ( log log T ) . result Upper bound matches previous lower bound of Ω ( d 2 T log T ) Ω(\sqrt{d^2 T\log T}) Ω ( d 2 T log T ) up to iterated logarithmic terms. Corrects pseudo log-likelihood method issues in various applications.
problem Log-likelihood function unbounded issues in pseudo log-likelihood methods.
method Provided a counterexample and corrected algorithms in previous literature.
result Ensured well-definedness of maximum pseudo log-likelihood estimation.
New algorithms for private generalized linear contextual bandits.
problem Private estimation and optimization for generalized linear models under differential privacy.
method Developed algorithms for stochastic and adversarial contexts under shuffle and joint differential privacy.
result Achieved private regret bounds for generalized linear models, differing from non-private rates by factors of d / ε \sqrt{d/\varepsilon} d / ε and d / ε \sqrt{d/\varepsilon} d / ε respectively. Improved student engagement detection using contextual and visual data.
problem Detecting students' behavioral engagement in real-world settings.
method Two-phase approach: contextual logs for active use, appearance information for engagement inference.
result Improved F1-scores from 0.77 to 0.82 with contextual information.
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.
Two algorithms for linear contextual bandits with rare updates achieve optimal regret and efficiency.
problem Linear contextual bandits with infrequent parameter updates.
method Two practical algorithms with O ( log log T ) O(\log\log T) O ( log log T ) updates, BLCE-G and BLCE. result Minimax-optimal regret with low computational complexity.
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 online pricing with contextual elasticity and heteroscedastic valuation.
problem Online contextual dynamic pricing with customer decision based on features and price.
method Introduced a novel approach to modeling customer demand with feature-based price elasticity and heteroscedastic noise. Proposed an efficient algorithm called Pricing with Perturbation (PwP).
result Proved an O ( d T log T ) O(\sqrt{dT\log T}) O ( d T log T ) regret bound for the algorithm, matching a lower bound of Ω ( d T ) Ω(\sqrt{dT}) Ω ( d T ) . A new estimator for evaluating policies in unknown environments.
problem Evaluating policies when both logging policy and value function are unknown.
method Doubly-Robust (DR) off-policy evaluation (OPE) estimator, DRUnknown, that estimates both the logging policy and value function.
result DRUnknown achieves the smallest asymptotic variance and is optimal when both models are correctly specified.
Extends OPE to evaluate policies using diverse logging data.
problem Evaluate policies using log data from different policies.
method Develops an OPE method for various logging policies.
result Method's predictions converge to true performance as sample size increases.
Develops a strategy to minimize loss in both stochastic and adversarial environments for linear contextual bandits.
problem Linear contextual bandits with adversarial corruption.
method Proposes a novel strategy called Best-of-Both-Worlds (BoBW) RealFTRL, extending RealLinExp3 and FTRL.
result Regret upper bound of $O\left(\min\left\{\frac{(\log(T))^3}{Δ_{*}} + \sqrt{\frac{C(\log(T))^3}{Δ_{*}}},\ \ \sqrt{T}(\log(T))^2
ight\}
ight)$ , showing effectiveness in both stochastic and adversarial environments.
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.
Two algorithms address limited adaptivity in generalized linear contextual bandits.
problem Limited adaptivity in generalized linear contextual bandits.
method Two algorithms, B-GLinCB and RS-GLinCB, designed for two settings of limited adaptivity.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret in both settings. Develops an anytime-valid framework for optimal policy identification from logged contextual bandit data.
problem Selecting the optimal policy from a candidate policy class while monitoring evidence continuously.
method Constructs a time-indexed set that retains the true optimal policy set uniformly over time.
result The procedure allows the analyst to monitor policy values, eliminate clearly suboptimal policies, and stop at data-dependent times without invalidating inference.
Develops a Best-of-Both-Worlds algorithm for linear contextual bandits with Tsallis entropy.
problem Linear contextual bandits with i.i.d. contexts.
method Follow-The-Regularized-Leader (FTRL) with Tsallis entropy.
result Achieves $O\left(\log(T)^{\frac{1+β}{2+β}}T^{\frac{1}{2+β}}
ight)$ regret under margin condition.
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state-of-the-art methods. However, many ques…
Modified Meta-TS for linear contextual bandits reduces regret.
problem Optimizing decision-making in dynamic environments with context vectors.
method Meta-TSLB algorithm for linear contextual bandits, analyzing Bayes regret.
result Derives an O ( ( m + log ( m ) ) n log ( n ) ) O((m+\log(m))\sqrt{n\log(n)}) O (( m + log ( m )) n log ( n ) ) bound on Bayes regret. AdaLinUCB optimizes exploration-exploitation for contextually varying costs.
problem Optimizing decision-making in environments with varying exploration costs.
method Adaptive Upper-Confidence-Bound (AdaLinUCB) algorithm for opportunistic learning.
result AdaLinUCB achieves O((log T)^2) regret bound, significantly outperforming other algorithms.
A new algorithm reduces inference error in adaptive contextual bandits.
problem Challenges in statistical inference for adaptive contextual bandits.
method Proposes a regularized EXP4 algorithm that satisfies the Lai-Wei stability condition.
result Valid Wald-type confidence intervals for linear functionals can be achieved without the price of adaptivity.
Contextual bandit methods fail with deficient support data.
problem Learning from support-deficient data in contextual bandits.
method Three approaches to IPS-based learning: action space restriction, reward extrapolation, and policy space restriction.
result Systematic analysis and empirical evaluation of approaches to IPS-based learning.
New method tackles high-dimensional contextual bandits with flexible kernel models.
problem Maximizing rewards in decision-making scenarios with many features.
method Introduces stochastic assumptions and no-regret learning for Gaussian kernels.
result Achieves no-regret learning even with feature dimensions growing with samples.
We consider the problem of contextual bandits with stochastic experts, which is a variation of the traditional stochastic contextual bandit with experts problem. In our problem setting, we assume access to a class of stochastic experts, where each expert is a conditional distribution over the arms given a context. We p…
New algorithm reduces regret in linear bandits by nearly optimal factors.
problem Optimizing regret in linear contextual bandits with limited actions.
method Variable-Confidence-Level (VCL) SupLinUCB algorithm.
result Regret matches minimax lower bound with iterated logarithmic factors.
This work improves online regression and contextual bandits using neural networks.
problem Improving online regression and contextual bandits using neural networks.
method Investigates neural networks for online regression, showing O ( log T ) \mathcal{O}(\log T) O ( log T ) regret for almost convex losses and KL loss. result Shows i l d e O ( K L ∗ + K ) ilde{\mathcal{O}}(\sqrt{KL^*} + K) i l d e O ( K L ∗ + K ) regret for NeuCB, outperforming existing algorithms. Improved regret bounds for adversarial linear contextual bandits.
problem Adversarial linear contextual bandits with changing loss functions.
method Truncated continuous exponential weights algorithm over the probability simplex, analyzing with linear bandit setting without contexts.
result Second-order bound of i l d e O ( K d V T ) ilde O(K\sqrt{d V_T}) i l d e O ( K d V T ) and first-order bound of i l d e O ( K d L T ∗ ) ilde O(K\sqrt{d L_T^*}) i l d e O ( K d L T ∗ ) . Ad exchanges use CORP to set reserve prices against strategic buyers.
problem Setting optimal reserve prices in ad exchanges with strategic buyers.
method Proposes CORP policy to learn and set reserve prices robustly.
result Achieves sublinear regret in unknown noise distribution.
Efficient algorithms for contextual slate bandits with limited adaptivity.
problem Contextual slate bandit problem with limited adaptivity.
method Proposed B-SlateGLinCB and RS-SlateGLinCB algorithms for batched and rarely-switching settings.
result Achieved regret bounds of O(Nd^(3/2)√T) and O(Nd√T) under diversity assumption.
A new algorithm for selecting top-k arms in extreme contextual bandits with improved efficiency.
problem Selecting top-k arms from a large set with contextual information and limited rewards.
method Proposes an algorithm for both non-extreme and extreme settings, using Inverse Gap Weighting and arm hierarchy models.
result Achieves improved regret guarantees for extreme settings with significant computational and statistical efficiency.
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.
Improved sample complexity for contextual combinatorial semi-bandits with sparse rewards.
problem Optimizing decisions in contexts with many possible actions and sparse rewards.
method Developed an algorithm for ( ε , δ ) (ε,δ) ( ε , δ ) -PAC variant of contextual combinatorial semi-bandits with improved sample complexity. result Achieved an ε ε ε -optimal policy with a sample complexity of i l d e O ( ( p o l y ( K / m ) + s m / ε 2 ) log ( ∣ Π ∣ / δ ) ) ilde{O}((poly(K/m)+sm/ε^2) \log(|Π|/δ)) i l d e O (( p o l y ( K / m ) + s m / ε 2 ) log ( ∣Π∣/ δ )) . New MAB algorithm for nonstationary, semiparametric reward models.
problem Nonstationary and non-linear reward models in sequential decision tasks.
method Contextual multi-armed bandit algorithm for semiparametric reward model.
result Proposed algorithm achieves a tight regret upper bound and performs well in simulations and real-world data.
MINs learn inverse mappings for high-dimensional optimization problems.
problem Data-driven optimization with high-dimensional inputs and valid subsets.
method Model Inversion Networks (MINs) learn an inverse mapping from scores to inputs.
result MINs can scale to high-dimensional input spaces and handle both offline and active data.
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . 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. Improved online Lasso reduces regret in sparse linear contextual bandits.
problem Sparse linear contextual bandit problem with inefficient sampling.
method Perturbed adversary approach to alleviate sampling inefficiency.
result Online Lasso achieves O ( k T log d ) \mathcal{O}(\sqrt{kT\log d}) O ( k T log d ) regret bound. 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. New method for sequential probability assignment reduces regret using contextual Shtarkov sums.
problem Minimizing regret in sequential probability assignment with arbitrary hypothesis classes.
method Introducing contextual Shtarkov sum and contextual Normalized Maximum Likelihood (cNML) algorithm.
result The contextual Shtarkov sum characterizes minimax regret and provides a minimax optimal strategy.
Motivated by online recommendation and advertising systems, we consider a causal model for stochastic contextual bandits with a latent low-dimensional confounder. In our model, there are L L L observed contexts and K K K arms of the bandit. The observed context influences the reward obtained through a latent confounder var…
A new linear contextual bandit algorithm with improved regret bound.
problem Efficiently solving linear contextual bandit problems with reduced regret.
method Proposes a novel estimator embedded with exploration and a self-normalized bound.
result Regret bound matches lower bound of Ω ( d T ) Ω(\sqrt{dT}) Ω ( d T ) up to logarithmic factors. Greedy algorithm achieves sublinear regret for various distributions.
problem Efficient performance of greedy algorithms in linear contextual bandit problems.
method Introduced Local Anti-Concentration (LAC) condition to ensure sublinear regret.
result Greedy algorithm achieves O ( poly log T ) O(\operatorname{poly} \log T) O ( poly log T ) cumulative expected regret. DOLCE improves off-policy evaluation and learning by decomposing effects.
problem Bias in off-policy evaluation and learning due to policy mismatch.
method Uses lagged contexts and a moment-based training procedure to decompose and cancel bias.
result DOLCE achieves substantial improvements in off-policy evaluation and learning.
We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K K K actions in response to the observed context, and observes the reward only for that chosen action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problem…
Malicious agents can manipulate linear contextual bandits to pull desired arms with logarithmic overhead.
problem Malicious attacks on linear contextual bandit algorithms in various domains.
method Study and propose an efficient algorithm to perform adversarial attacks on linear contextual bandits.
result Malicious agents can force a linear contextual bandit algorithm to pull any desired arm T − o ( T ) T - o(T) T − o ( T ) times over a horizon of T T T steps with logarithmic modifications. New methods for anytime-valid off-policy inference in contextual bandits.
problem Estimating properties of hypothetical policies in adaptive experiments.
method Modern martingale techniques for comprehensive OPE inference.
result Valid anytime inference for off-policy mean reward values and entire reward distributions.
A novel bandit problem with context-dependent rewards and blocking.
problem Contextual bandit problem with blocking.
method Online bipartite matching, UCB algorithm, delayed exploitation, opportunistic subsampling.
result Guaranteed O ( log T ) \mathcal{O}(\log T) O ( log T ) -regret in bandit setting. New loss functions optimize pricing policies using transaction data, ensuring expected revenue guarantees.
problem Optimizing pricing policies with transaction data where valuation data is not directly observed.
method Introducing convex loss functions for contextual pricing, focusing on log-concave valuation distributions.
result Proved expected revenue bounds for generalized hinge and quantile pricing loss functions.