Proposes a neural network for contextual regression.
problem Improving model efficiency and interpretability in regression with contextual features.
method Simple contextual neural network (SCtxtNN) that separates context identification from context-specific regression.
result SCtxtNN achieves lower excess mean squared error and more stable performance than feed-forward neural networks.
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.
New algorithm for contextual bandits with linear constraints using regression.
problem Contextual bandits with packing and covering constraints.
method Modular Lagrangian approach via regression.
result First vanishing-regret guarantees for CBwLC (or CBwK).
A fundamental challenge in contextual bandits is to develop flexible, general-purpose algorithms with computational requirements no worse than classical supervised learning tasks such as classification and regression. Algorithms based on regression have shown promising empirical success, but theoretical guarantees have…
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.
Universal algorithm learns unknown distribution for various decision-making problems.
problem Various statistical measures in contextual sequential decision-making.
method Infinite-dimensional functional regression oracle for cumulative distribution functions.
result Utility regret rate bounded by polynomial decay of eigenvalue sequence.
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 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. 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. Optimal algorithm for maximizing rewards in contextual bandits with resource constraints.
problem Maximizing rewards in contextual bandits with resource constraints.
method Proposed a universal and optimal algorithmic framework for CBwK by reducing it to online regression.
result Established the optimality of the proposed algorithm for various function classes.
New algorithms adapt to model misspecification in contextual bandits.
problem Design efficient algorithms for contextual bandits that handle model misspecification gracefully.
method Oracle-efficient algorithms for ε-misspecified contextual bandits using square loss regression.
result First algorithm achieving optimal regret bound for unknown misspecification level in linear contextual bandits.
This paper achieves optimal regret bounds for locally private linear contextual bandit.
problem Designing locally private linear contextual bandit algorithms with optimal regret bounds.
method New algorithmic and analytical ideas, including mean absolute deviation analysis and layered principal component regression.
result Achieves an i l d e O ( T ) ilde O(\sqrt{T}) i l d e O ( T ) regret upper bound for locally private linear contextual bandit. New algorithms robust to adversarial data achieve optimal performance.
problem Adversarial robustness in high-dimensional online learning problems.
method Alternating minimization scheme combining least-squares and convex reweighting.
result Achieves optimal robustness guarantees without distributional assumptions.
This paper investigates how transformers can learn to generalize to unseen examples in context.
problem Understanding how transformers can generalize to unseen examples in a prompt.
method Gradient descent analysis of one-layer multi-head transformers for in-context learning.
result The training loss for a one-layer multi-head transformer converges linearly to a global minimum, effectively learning ridge regression over basis functions.
Efficient algorithm for contextual bandits with first-order guarantees.
problem Adapting to low noise in contextual bandits.
method Reduction to online regression with logarithmic loss.
result Optimal and efficient first-order guarantees for contextual bandits.
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.
We improve optimization for data with varying variance.
problem Optimizing data with varying variance.
method Generalized learning and optimization frameworks for data-driven optimization.
result Asymptotic and finite sample guarantees for stochastic programs.
New bandit algorithm works without realizability assumption.
problem Contextual bandit problems without realizability assumption.
method Computes a constrained regression problem in every epoch, ensuring similar regret guarantees as realizability-based algorithms.
result Ensures similar regret guarantees as realizability-based algorithms, up to a misspecification term.
Optimal multitask learning method for sparse heterogeneous datasets.
problem Efficiently learning from multiple related datasets with sparse task-specific differences.
method MOLAR estimator, combining weighted median and shrinkage.
result Improves estimation error dependence on data dimension compared to task-wise least squares.
The paper develops a robust algorithm for contextual bandits with heavy-tailed rewards.
problem Contextual bandits with heavy-tailed rewards.
method Develops an algorithm based on Catoni's estimator for robust statistics, applying it to contextual bandits with general function approximation.
result Establishes regret bounds that depend on cumulative reward variance and logarithmically on the reward range and number of rounds.
New method for private linear regression under privacy constraints, achieving optimal rates.
problem Statistical complexity of private linear regression under unknown, ill-conditioned covariates.
method Information-Weighted Regression method
result Optimal convergence rates for both central and local privacy models.
Classic contextual bandit algorithms for linear models, such as LinUCB, assume that the reward distribution for an arm is modeled by a stationary linear regression. When the linear regression model is non-stationary over time, the regret of LinUCB can scale linearly with time. In this paper, we propose a novel multisca…
Improved Thompson Sampling reduces regret in contextual bandits and reinforcement learning.
problem Thompson Sampling's exploration is insufficient in some contexts.
method Developed Feel-Good Thompson Sampling to address exploration issues.
result Feel-Good Thompson Sampling reduces regret compared to standard Thompson Sampling.
Novel framework for contextual anomaly detection models uncertainty.
problem Identifying anomalies in target variables influenced by contextual variables.
method Normalcy score (NS) framework using heteroscedastic Gaussian process regression.
result NS outperforms state-of-the-art methods in detection accuracy and interpretability.
New algorithm reduces linear contextual bandit regret with adversarial corruption.
problem Linear contextual bandit with adversarial reward corruption.
method Optimism in the face of uncertainty principle, weighted ridge regression.
result Achieves nearly optimal regret for both corrupted and uncorrupted cases.
A new method for decision-focused learning reduces computational cost.
problem Efficiently solving combinatorial problems with uncertain parameters.
method Reframed as cost-sensitive multi-output regression, with novel loss components.
result Comparable downstream task quality with reduced computational cost.
BFTS uses Bayesian Additive Regression Trees for improved personalized mobile health interventions.
problem Adapting to complex, non-linear user behaviors in personalized mobile health interventions.
method Bayesian Forest Thompson Sampling (BFTS) integrates Bayesian Additive Regression Trees (BART) into the exploration loop of contextual bandits.
result BFTS achieves state-of-the-art regret on tabular benchmarks and improves engagement rates by over 30% in a behavioral intervention study.
A major challenge in contextual bandits is to design general-purpose algorithms that are both practically useful and theoretically well-founded. We present a new technique that has the empirical and computational advantages of realizability-based approaches combined with the flexibility of agnostic methods. Our algorit…
Develops algorithms for CCBs with non-linear costs, improving safety and performance.
problem Safety constraints in sequential decision making with non-linear arm costs.
method Innovative algorithms using Inverse Gap Weighting (IGW) and online regression oracle.
result Sub-linear regret bounds for C-SquareCB and first-order regret for C-FastCB.
We use surrogate losses to obtain several new regret bounds and new algorithms for contextual bandit learning. Using the ramp loss, we derive new margin-based regret bounds in terms of standard sequential complexity measures of a benchmark class of real-valued regression functions. Using the hinge loss, we derive an ef…
Improved algorithms for dynamic pricing under different valuation models.
problem Maximizing revenue in dynamic pricing with contextual information.
method Developed algorithms for two valuation models: linearly dependent with noise and Hölder continuous.
result Achieved optimal regret bounds for both models, improving existing results.
Algorithm reduces regret in misspecified linear contextual bandits.
problem Misspecified linear contextual bandits with bounded misspecification.
method Data selection scheme for online regression, leveraging uncertainty.
result Regret bound of O ~ ( d 2 / Δ ) \tilde O(d^2/Δ) O ~ ( d 2 /Δ ) when ζ ≤ O ~ ( Δ / d ) ζ \leq \tilde O(Δ/\sqrt{d}) ζ ≤ O ~ ( Δ/ d ) . New method for evaluating and learning in complex decision-making scenarios.
problem Evaluating and learning from policies in contextual combinatorial bandits with high bias and variance.
method Factored action space decomposition and importance sampling-based estimator (OPCB).
result OPCB achieves superior performance in OPE and OPL compared to conventional methods.
Contextual bandits are widely used in Internet services from news recommendation to advertising, and to Web search. Generalized linear models (logistical regression in particular) have demonstrated stronger performance than linear models in many applications where rewards are binary. However, most theoretical analyses …
Machine learning algorithms such as linear regression, SVM and neural network have played an increasingly important role in the process of scientific discovery. However, none of them is both interpretable and accurate on nonlinear datasets. Here we present contextual regression, a method that joins these two desirable …
New method for online statistical inference in contextual bandits using SGD.
problem Online decision-making in contextual bandits with statistical inference.
method Weighted stochastic gradient descent for adaptive data collection.
result Asymptotic normality of the parameter estimator with improved efficiency.
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.
Motivated by the application of real-time pricing in e-commerce platforms, we consider the problem of revenue-maximization in a setting where the seller can leverage contextual information describing the customer's history and the product's type to predict her valuation of the product. However, her true valuation is un…
Proposes EE-Net for neural exploration in contextual bandits.
problem Exploitation-Exploration tradeoff in contextual bandits.
method Uses two neural networks: Exploitation and Exploration, to learn reward function and adaptively explore.
result Achieves O ( T log T ) \mathcal{O}(\sqrt{T\log T}) O ( T log T ) regret and outperforms existing methods. FGTSVA improves Thompson Sampling for contextual bandits with optimal variance-aware regret.
problem Optimizing regret bounds for Thompson Sampling in contextual bandits.
method Developed FGTSVA, a variance-aware Thompson Sampling algorithm for contextual bandits with a new decoupling coefficient.
result Achieved optimal regret bound of i l d e O ( d c ⋅ log ∣ F ∣ ∑ t = 1 T σ t 2 + d c ) ilde{O}(\sqrt{\mathrm{dc}\cdot\log|\mathcal{F}|\sum_{t=1}^Tσ_t^2}+\mathrm{dc}) i l d e O ( dc ⋅ log ∣ F ∣ ∑ t = 1 T σ t 2 + dc ) . Prominently used in support vector machines and logistic regressions, kernel functions (kernels) can implicitly map data points into high dimensional spaces and make it easier to learn complex decision boundaries. In this work, by replacing the inner product function in the softmax layer, we explore the use of kernels …
This work explores adaptations of successful multi-armed bandits policies to the online contextual bandits scenario with binary rewards using binary classification algorithms such as logistic regression as black-box oracles. Some of these adaptations are achieved through bootstrapping or approximate bootstrapping, whil…
POTEC tackles off-policy learning in large action spaces, improving effectiveness.
problem Existing OPL methods fail in large discrete action spaces due to bias or variance issues.
method Two-stage algorithm: cluster selection via policy-based approach, action selection via regression-based approach.
result POTEC provides substantial improvements in off-policy learning effectiveness, especially in large and structured action spaces.
This work bridges federated learning and contextual bandits, enhancing FL's utility.
problem Limited use of federated learning in contextual bandits despite its potential.
method Proposes FedIGW, a novel federated contextual bandits design that leverages regression-based algorithms and integrates various FL components.
result FedIGW better harnesses FL innovations and provides flexible, modular, and seamless integration of FL elements.
A new algorithm uses concavity in Gaussian processes to optimize decisions in bandit problems.
problem Optimizing decisions in sequential problems with context-dependent rewards.
method Proposes a UCB algorithm using a shape-constrained reward function estimator based on a Gaussian Process model with concavity constraints.
result Derives regret bounds for the proposed UCB algorithm.
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.
LLM-Lasso uses LLMs to improve feature selection in Lasso regression.
problem Improving feature selection in Lasso regression with domain-specific knowledge.
method Combines LLMs with Lasso regularization to generate feature weights.
result Outperforms standard Lasso and feature selection baselines in biomedical studies.
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.