We introduce the safe linear stochastic bandit framework---a generalization of linear stochastic bandits---where, in each stage, the learner is required to select an arm with an expected reward that is no less than a predetermined (safe) threshold with high probability. We assume that the learner initially has knowledg…
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,695 papers · 148 categories
Trend · papers per month
48 results for “safe linear bandits”
Bandit algorithms have various application in safety-critical systems, where it is important to respect the system constraints that rely on the bandit's unknown parameters at every round. In this paper, we formulate a linear stochastic multi-armed bandit problem with safety constraints that depend (linearly) on an unkn…
Safe Gaussian Process Bandit Optimization with sub-linear regret bounds.
problem Sequential decision-making under uncertainty and safety constraints.
method Developed SGP-UCB, a safe variant of GP-UCB with modifications to respect safety constraints.
result First sub-linear regret bounds for safe Gaussian Process Bandit Optimization.
Safe linear bandits over unknown polytopes avoid safety violations and suboptimal actions.
problem Online approach to linear programming with unknown constraints and risks.
method Doubly-optimistic strategy (DOSS) for safe linear bandits over polytopes.
result DOSS achieves tight bounds on efficacy regret and safety violations.
The design and performance analysis of bandit algorithms in the presence of stage-wise safety or reliability constraints has recently garnered significant interest. In this work, we consider the linear stochastic bandit problem under additional \textit{linear safety constraints} that need to be satisfied at each round.…
Safety is a desirable property that can immensely increase the applicability of learning algorithms in real-world decision-making problems. It is much easier for a company to deploy an algorithm that is safe, i.e., guaranteed to perform at least as well as a baseline. In this paper, we study the issue of safety in cont…
Study best arm identification with safety constraints in bandit problems.
problem Real-world decision-making with safety constraints.
method Analyzed linear and monotonic reward and safety constraints, proposed algorithms.
result Guaranteed safe learning in both linear and general reward/safety constraint settings.
A decentralized algorithm minimizes cumulative regret in stochastic linear bandits with safety constraints.
problem Efficiently solving a linear bandit-optimization problem over a network of agents with safety constraints.
method DLUCB: a fully decentralized algorithm that minimizes cumulative regret through UCB strategy and consensus procedure.
result Near-optimal regret performance of with communication rate.
Investigates safe decision-making in interactive environments.
problem Learning the best safe decision in real-time systems.
method Reduces to a constrained linear bandits problem, proposes adaptive experimental design-based algorithm.
result First results on best-arm identification in linear bandits with safety constraints.
Safe actions learned in finite trials, without infinite exploration.
problem Learning safe actions in unknown environments efficiently.
method Defining a handicap metric and using sequential probability ratio test for discarding unsafe actions.
result Achieves constant handicap, discarding unsafe machines with probability one in finite rounds.
Two new algorithms optimize rewards while respecting safety constraints in sequential decisions.
problem Optimizing rewards with safety constraints in sequential decisions.
method Stage-wise conservative linear Thompson Sampling (SCLTS) and stage-wise conservative linear UCB (SCLUCB).
result Probabilistic regret bounds of order O(\sqrt{T} \log^{3/2}T) and O(\sqrt{T} \log T).
Paper tackles safe combinatorial semi-bandits with risk constraints.
problem Safe combinatorial semi-bandits with risk constraints.
method Formulated probably anytime-safe constraint, designed PASCombUCB algorithm.
result PASCombUCB is almost asymptotically optimal in minimizing regret.
ACOL learns constraints from human preferences in driving simulations.
problem Learning constraints from human preferences in driving simulations.
method Adaptive Constraint Learning (ACOL) algorithm for constrained linear best-arm identification.
result ACOL's sample complexity matches worst-case lower bound and is significantly tighter in the average case.
In this paper we introduce the transductive linear bandit problem: given a set of measurement vectors , a set of items , a fixed confidence , and an unknown vector , the goal is to infer $\text{argmax}_{z\in \mathcal{Z}} z^\t…
Safe and Adaptive Decision-Making for Optimization of Safety-Critical Systems: The ARTEO Algorithmcs.LG
ARTEO algorithm optimizes safety-critical systems with uncertainty.
problem Decision-making under uncertainty with safety constraints in real-time optimization.
method ARTEO algorithm uses multi-armed bandits as a mathematical programming problem subject to safety constraints, learning unknown characteristics through exploration and incorporating uncertainty quantification.
result ARTEO achieves less cumulative regret with accurate and safe decisions.
Develops confidence bounds for off-policy evaluation in contextual bandits.
problem Evaluating policies that were not used to collect data.
method Martingale analysis for non-asymptotic, non-parametric, and valid confidence sequences.
result Empirically tight bounds on failure probability and width.
In this paper, we study the problem of safe online learning to re-rank, where user feedback is used to improve the quality of displayed lists. Learning to rank has traditionally been studied in two settings. In the offline setting, rankers are typically learned from relevance labels created by judges. This approach has…
Logarithmic regret strategies for safe multi-armed bandits with safety risk constraints.
problem Maximizing reward while avoiding unsafe arms under safety risk constraints.
method Doubly optimistic strategies with pseudo-regret formulation.
result Logarithmic regret bounds for safe multi-armed bandits.
Agents collaborate to minimize regret while keeping costs under a threshold.
problem Collaborative multi-agent stochastic linear bandits with cost constraints.
method Safe distributed upper confidence bound algorithm (MA-OPLB) with accelerated consensus.
result Regret bound of order $ \mathcal{O}\left(\frac{d}{τ-c_0}\frac{\log(NT)^2}{\sqrt{N}}\sqrt{\frac{T}{\log(1/|λ_2|)}}
ight)$.
New algorithm tackles batched stochastic linear bandits with 1-bit communication constraints.
problem Stochastic linear bandits with 1-bit communication constraints.
method Phased-elimination algorithms based on G-optimal designs and 1-bit mean estimation.
result Achieves near-optimal regret bounds for broad scaling regimes.
Accelerating Non-Negative and Bounded-Variable Linear Regression Algorithms with Safe Screeningcs.LG
The paper accelerates regression algorithms by identifying saturated coordinates.
problem Non-negative and bounded-variable linear regression problems.
method Safe screening technique to identify saturated coordinates.
result The approach provides theoretical guarantees for identifying saturated coordinates.
New algorithm optimizes reward while ensuring safety in complex decision-making problems.
problem Maximizing reward while adhering to safety constraints in complex decision-making problems.
method Optimistic Primal-Dual Proximal Policy Optimization (OPDOP) algorithm combining least-squares policy evaluation and a bonus term for safe exploration.
result Achieves regret and constraint violation.
Safe RL in linear systems achieves -regret.
problem Efficiently learning in safety-constrained online reinforcement learning.
method Study of linear quadratic regulator with safety constraints.
result First safe algorithm with -regret.
Adaptive smooth non-stationary bandits achieve optimal regret rates without knowing parameters.
problem Smooth non-stationary bandits with Hölder class rewards.
method Established optimal dynamic regret rate and adaptive algorithm.
result Optimal dynamic regret can be attained adaptively without knowing Hölder exponent and coefficient.
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.
High dimensional regression benefits from sparsity promoting regularizations. Screening rules leverage the known sparsity of the solution by ignoring some variables in the optimization, hence speeding up solvers. When the procedure is proven not to discard features wrongly the rules are said to be \emph{safe}. In this …
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 .
A new algorithm optimizes local objectives in federated learning with heterogeneous clients.
problem Optimizing local objectives in federated learning with heterogeneous client data.
method Proposes PF-PNE algorithm with double elimination strategy.
result PF-PNE algorithm optimizes local objectives with arbitrary heterogeneity and protects client data confidentiality.
A new distributed method speeds up sparse model training.
problem Efficiently training models with massive samples and high-dimensional features.
method Distributed Dynamic Safe Screening (DDSS) method for sparsity regularized models.
result Achieves linear convergence rate and eliminates almost all inactive features.
Optimal algorithm for identifying best arm in stochastic linear bandits with fixed confidence.
problem Identifying the best arm in stochastic linear bandits with fixed confidence.
method Extending an algorithm designed for Best Arm Identification to the -Thresholding Bandit Problem (TBP).
result Asymptotically optimal algorithm for TBP.
New attack manipulates UCB algorithm, new defense algorithm reduces pseudo-regret.
problem Adversarial attacks on stochastic bandit algorithms.
method Introducing action-manipulation attacks and proposing a robust defense algorithm.
result Proposed defense algorithm reduces pseudo-regret to O(max{log T, A}).
Learning Modular Safe Policies in the Bandit Setting with Application to Adaptive Clinical Trialscs.LG
The stochastic multi-armed bandit problem is a well-known model for studying the exploration-exploitation trade-off. It has significant possible applications in adaptive clinical trials, which allow for dynamic changes in the treatment allocation probabilities of patients. However, most bandit learning algorithms are d…
This work establishes safe reinforcement learning for LQR with nonlinear baselines.
problem Safe reinforcement learning in LQR with unknown dynamics and safety constraints.
method General framework for nonlinear baselines, focusing on 1D spaces.
result Achieves optimal regret bounds for constrained reinforcement learning.
The paper provides a non-asymptotic error bound for linear system identification under nonlinear policies.
problem System identification for linear systems with nonlinear and/or time-varying policies under i.i.d. random excitation noises.
method Least square estimation with non-asymptotic error bound for bounded state and action trajectories.
result The error bound is consistent with linear policies and generalizes existing guarantees.
New algorithms tackle RKHS bandits with reduced complexity and improved performance.
problem Adversarial and stochastic RKHS bandit problems with high computational complexity.
method Combining approximation theory with misspecified linear bandit methods.
result First general algorithm for adversarial RKHS bandit problem.
Paper tackles LDP bandits learning with improved results and sub-linear regret.
problem Contextual bandits learning with LDP privacy constraints.
method Simple black-box reduction frameworks for context-free bandits, extended to GLB.
result First result for BCO with multi-point feedback under LDP, sub-linear regret for GLB.
First robust bandit algorithm for contextual bandits with sub-linear regret.
problem Vulnerability of linear contextual bandit algorithms to adversarial attacks.
method Proposes a robust bandit algorithm for stochastic linear contextual bandits under fully adaptive and omniscient attacks.
result Sub-linear regret under various attacks without requiring attack information.
New algorithms improve linear bandit performance with low computation.
problem Optimizing reward in linear stochastic bandits.
method Reward-biased maximum likelihood method modified for linear and generalized linear bandits.
result New policies achieve order-optimality and competitive empirical performance.
Optimal and safe semi-supervised learning estimator for high-dimensional data.
problem Improving regression parameter estimation with unlabeled data in high-dimensional settings.
method Established minimax lower bound, proposed optimal and safe semi-supervised estimators.
result Optimal semi-supervised estimator achieves the minimax lower bound.
In high dimensional regression settings, sparsity enforcing penalties have proved useful to regularize the data-fitting term. A recently introduced technique called screening rules propose to ignore some variables in the optimization leveraging the expected sparsity of the solutions and consequently leading to faster s…
Study non-linear combinatorial bandits with polynomial rewards, finding significant differences from linear cases.
problem Adversarial combinatorial bandits with general non-linear reward functions.
method Extending existing work on adversarial linear combinatorial bandits, analyzing minimax optimal regret for polynomial and non-polynomial reward functions.
result Minimax optimal regret bounds for adversarial combinatorial bandits with general non-linear reward functions.
Safe screening rules reduce -regression computation by fixing 76% of variables.
problem Efficiently solving -regression problems with large datasets.
method Convex relaxation and safe screening rules to eliminate variables.
result 76% of variables can be fixed to their optimal values, reducing computational burden.
Unified approach for non-stationary linear bandits with dynamic regret.
problem Non-stationary linear bandits with round-specific feasible actions and drifting reward models.
method Unified misspecification-reduction viewpoint, restarting algorithms with misspecification-dependent regret guarantees.
result Optimal \(T^{2/3}P_T^{1/3}\) dynamic-regret dependence for both linear bandits and contextual linear bandits.
Bayesian bandit algorithms with approximate inference improve regret bounds in stochastic linear bandits.
problem Theoretical justification for Bayesian bandit algorithms with approximate inference in stochastic linear bandits.
method Proposed a theoretical framework to analyze approximate inference impact and conducted frequentist regret analysis on LinTS and LinBUCB.
result LinTS and LinBUCB preserve their original regret upper bounds with larger constant terms in approximate inference settings.
Safe imitation learning with a safety layer for flexible training.
problem Flexible yet safe imitation learning for complex tasks.
method Theory and modular method with a safety layer for continuous policy, adversarial training, and worst-case safety guarantees.
result Robustness advantage of safety layer during training compared to test time.
Develops new methods for risk-aware decision-making in medical bandits.
problem Risk-averse decision-making in medical contexts with limited data.
method Safe, anytime-valid concentration bounds, risk-aware contextual bandits, nonparametric algorithms.
result Improved decision-making algorithms for postoperative patient follow-up.
A new algorithm improves stochastic linear bandit performance using residual bootstrap.
problem Improving performance in stochastic linear bandit problems.
method Residual bootstrap exploration to estimate mean reward and pull the arm with the highest estimate.
result Proposed algorithm exttt{LinReBoot} achieves high-probability sub-linear regret under mild conditions.
Optimizes pure exploration in linear bandits with a new algorithm.
problem Best-arm identification in linear stochastic bandits.
method Developed the first asymptotically optimal algorithm for fixed-confidence pure exploration in linear bandits.
result Avoids the pitfall of a simple but difficult instance and bypasses the need to solve an optimal design problem.