Linear contextual bandit is an important class of sequential decision making problems with a wide range of applications to recommender systems, online advertising, healthcare, and many other machine learning related tasks. While there is a lot of prior research, tight regret bounds of linear contextual bandit with infi…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Contextual Action-Set”
Algorithm optimizes bandit decisions with changing action sets using Gaussian processes.
problem Optimizing decisions in a bandit problem with time-varying action sets.
method Proposes an algorithm called O'CLOK-UCB using Gaussian processes to handle changing action sets and contexts.
result Achieves regret bound of with high probability.
Improved reinforcement learning for episodes with varying action sets.
problem Reinforcement learning with context-dependent action sets.
method Extends MVP algorithm to handle adversarial and stochastic contexts.
result Established minimax regret bounds of for adversarial contexts.
New method achieves near-optimal regret without simulator.
problem Adversarial linear contextual bandits with unknown loss vectors.
method Near-optimally reduces regret to sqrt(T) without simulator.
result Achieves regret of sqrt(T) without simulator, improving existing methods.
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.
Efficient algorithms for contextual bandits with smooth regret in continuous action spaces.
problem Efficient learning in large or continuous action spaces.
method Smooth regret notion and efficient algorithms for general function approximation.
result Statistically and computationally efficient algorithms for contextual bandits with smooth regret.
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.
A federated learning algorithm tackles linear bandits with adversarial actions, achieving optimal regret bounds.
problem Federated linear bandits with finite adversarial action sets.
method FedSupLinUCB algorithm, extending SupLinUCB and OFUL principles.
result Achieves a total regret of , matching minimax lower bound and being order-optimal.
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.
Optimal algorithm for contextual bandits with unknown context distributions.
problem Designing efficient algorithms for contextual bandits with unknown context distributions.
method Cross-learning setting, novel technique for coordinating multiple epochs.
result Nearly tight regret bound of for learning to bid in first-price auctions and sleeping bandits.
Study contextual bandits with stage-wise constraints, proving regret bounds and extending results.
problem Contextual bandits with stage-wise constraints in high probability and expectation settings.
method Upper-confidence bound algorithms for linear and non-linear reward/cost functions, extending to multiple constraints.
result Regret bounds for various settings, including non-linear reward/cost functions.
We propose a new framework for designing estimators for off-policy evaluation in contextual bandits. Our approach is based on the asymptotically optimal doubly robust estimator, but we shrink the importance weights to minimize a bound on the mean squared error, which results in a better bias-variance tradeoff in finite…
Soft Actor-Critic is a state-of-the-art reinforcement learning algorithm for continuous action settings that is not applicable to discrete action settings. Many important settings involve discrete actions, however, and so here we derive an alternative version of the Soft Actor-Critic algorithm that is applicable to dis…
In many real-world sequential decision making problems, the number of available actions (decisions) can vary over time. While problems like catastrophic forgetting, changing transition dynamics, changing rewards functions, etc. have been well-studied in the lifelong learning literature, the setting where the action set…
The (contextual) multi-armed bandit problem (MAB) provides a formalization of sequential decision-making which has many applications. However, validly evaluating MAB policies is challenging; we either resort to simulations which inherently include debatable assumptions, or we resort to expensive field trials. Recently …
The Markov decision process (MDP) formulation used to model many real-world sequential decision making problems does not efficiently capture the setting where the set of available decisions (actions) at each time step is stochastic. Recently, the stochastic action set Markov decision process (SAS-MDP) formulation has b…
We study the linear contextual bandit problem with finite action sets. When the problem dimension is , the time horizon is , and there are candidate actions per time period, we (1) show that the minimax expected regret is for every algorithm, and (2) introduce a V…
We achieve a finite regret bound of O(dlogd) for online inverse linear optimization with M-convex action sets.
problem Online inverse linear optimization with M-convex action sets.
method Combining structural characterization of optimal solutions on M-convex sets with geometric volume argument.
result Finite regret bound of O(dlogd) for online inverse linear optimization with M-convex action sets.
A new algorithm balances global reward and group constraints in federated multi-armed bandits.
problem Maximizing global reward while protecting client privacy in federated learning.
method Combinatorial contextual bandit with group constraints, using a two-output Gaussian process.
result TCGP-UCB incurs low regret, balancing super arm reward and group reward constraints.
New STDP rule for spiking neurons solves discrete action reinforcement learning tasks.
problem Applying standard STDP to discrete action reinforcement learning tasks.
method Feedback-modulated TD-STDP learning rule for spiking neuron networks.
result Feedback modulation improves credit assignment in reinforcement learning.
Ensemble++ uses shared-factor ensembles to scale Thompson Sampling for linear and nonlinear bandits.
problem Computational challenges in Thompson Sampling for large-scale or non-conjugate settings.
method Ensemble++ with shared-factor architecture and random linear combinations.
result Ensemble++ achieves comparable regret to exact Thompson Sampling with significantly smaller ensemble sizes.
Efficient algorithms for online learning with changing action sets, achieving no-approximate-regret guarantees.
problem Online learning with sleeping experts/bandits, where only a subset of actions are available each time.
method Developed computationally efficient algorithms providing no-approximate-regret guarantees for the general problem and better approximation ratios for special cases.
result Achieved no-approximate-regret guarantees for the general sleeping expert/bandit problems and better approximation ratios for specific cases.
New algorithms for stochastic linear bandits with heavy-tailed payoffs achieve nearly optimal regret.
problem Stochastic linear bandits with heavy-tailed payoffs.
method Median of means and dynamic truncation.
result Sublinear regret bound of for .
New method for linear bandits with unknown sparsity, improving sparse regret bounds.
problem Sparse regret bounds for unknown sparsity and adversarial action sets.
method Combines online to confidence set conversions with randomized model selection over nested confidence sets.
result First sparse regret bounds for unknown sparsity and adversarial action sets.
New algorithm identifies optimal actions in large reward spaces efficiently.
problem Finding the best action from a large set of options with minimal trials.
method GenTS-Explore algorithm for real-valued combinatorial pure exploration.
result Achieves optimal sample complexity for large action sets.
TRAiL is a linear bandit algorithm that ensures optimal regret and guarantees inference quality.
problem Optimal regret and inference quality in linear bandits with convex action sets.
method TRAiL estimates the parameter through regularized least squares and perturbs the action set along the tangent plane.
result TRAiL achieves an upper bound on cumulative regret with high probability.
New method reduces ensemble size for linear bandits, achieving near optimal regret.
problem Achieving near optimal regret in linear bandits with limited ensemble size.
method Ensemble sampling with a size of order for a -dimensional stochastic linear bandit.
result Regret is at most , improving over linear scaling with .
We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order for any finite action set with actions, under the assumption that the instantaneous loss is bounded by 1. This…
New reinforcement learning framework for adapting to new actions.
problem Making reinforcement learning agents adaptable to new actions without retraining.
method Two-stage framework: infer action representations first, then train a flexible policy.
result Agents can make decisions from new action sets without retraining.
Motivated by the recent applications of game-theoretical learning techniques to the design of distributed control systems, we study a class of control problems that can be formulated as potential games with continuous action sets, and we propose an actor-critic reinforcement learning algorithm that provably converges t…
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…
Lower bounds on eigenspectrum show rich action spaces force polynomial regret in linear bandits.
problem Understanding the minimum eigenvalue growth in linear bandits with rich action sets.
method Non-asymptotic lower bound on eigenspectrum of design matrix.
result Minimum eigenvalue of expected design matrix grows as for sub-linear regret.
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.
New algorithm reduces sleeping bandits' regret to O(sqrt(T)).
problem Improving sleeping bandits with stochastic actions and adversarial rewards.
method Inspired by EXP3, new algorithm with regret.
result Achieves regret, improving over existing .
Efficient algorithm converges to Nash equilibrium in bilinear problems with bandit feedback.
problem Learning dynamics in bilinear saddle-point problems with bandit feedback.
method Uncoupled learning algorithm combining experimental design and FTRL with a tailored regularizer.
result Last-iterate convergence rate of in high probability.
Contextualized ML learns context-dependent effects using deep learning.
problem Learning heterogeneous and context-dependent effects in data.
method Applying deep learning to the meta-relationship between contextual information and context-specific parametric models.
result Unified framework for cluster analysis and cohort modeling.
IDS improves reinforcement learning with contextual information.
problem Optimizing IDS for contextual reinforcement learning.
method Investigated contextual bandit problems and proposed a computationally-efficient IDS.
result Contextual IDS outperforms conditional IDS by considering future contexts.
The paper tackles Nash-regret minimization in congestion games with bandit feedback.
problem Minimizing Nash-regret in congestion games with bandit feedback.
method Proposes centralized and decentralized algorithms for congestion games with bandit feedback, and a centralized algorithm for Markov congestion games.
result Sample complexity depends polynomially on the number of players and facilities, not the size of the action set.
SADCBO optimizes contextual variables by balancing relevance and cost.
problem Optimizing contextual variables with varying costs and unknown relevance.
method Adaptive selection of relevant contextual variables using sensitivity analysis and early stopping.
result Consistent improvement in optimization across various examples.
The use of Reinforcement Learning in real-world scenarios is strongly limited by issues of scale. Most RL learning algorithms are unable to deal with problems composed of hundreds or sometimes even dozens of possible actions, and therefore cannot be applied to many real-world problems. We consider the RL problem in the…
The bundle approach and n-contextuality reveal quantum model contextuality.
problem Understanding contextuality in quantum models using topology.
method Using the bundle approach, we describe contextuality as the non-existence of global sections in the measure bundle. We introduce n-contextuality to explore model dependence on scenario topology.
result Quantum theory and GHZ models exhibit all levels of n-contextuality, showing contextuality is related to holonomy group non-triviality.
Algorithm identifies best arm in combinatorial bandits with semi-bandit feedback.
problem Identifying the best arm in combinatorial bandits with semi-bandit feedback.
method Interpreted as a sequential zero-sum game, developed a CombGame meta-algorithm with finite time guarantees.
result First computationally efficient algorithm that is asymptotically optimal and has competitive empirical performance.
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.
Paper tackles domain adaptation for contextual bandits with sub-linear regret.
problem Adapting contextual bandit algorithms across domains with distribution shift.
method Learn a bandit model for the target domain using feedback from the source domain.
result Sub-linear regret bound maintained across domains.
Transformers model contextual relations using probabilistic measures, revealing their expressive power.
problem Lack of clear understanding of Transformer's ability to model contextual relations.
method Introduced a measure-theoretic framework connecting softmax attention and entropy-regularized optimal transport.
result Transformer architectures can approximate arbitrary contextual relations, and the choice of normalization affects how these relations are represented.
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 .
The study explores whether model selection guarantees apply to contextual bandits.
problem Applying model selection guarantees to contextual bandits.
method Investigates whether similar guarantees for model selection in statistical learning can be extended to contextual bandit learning.
result Initial findings suggest that model selection guarantees may not directly apply to contextual bandits.
Algorithm finds optimal regularizers for online linear optimization.
problem Finding optimal regularizers to minimize regret in online linear optimization.
method Algorithm takes input sets and outputs an optimal regularizer for FTRL.
result Algorithm guarantees regret within a constant factor of the best possible learning algorithm.