In this short note we consider a dynamic assortment planning problem under the capacitated multinomial logit (MNL) bandit model. We prove a tight lower bound on the accumulated regret that matches existing regret upper bounds for all parameters (time horizon , number of items and maximum assortment capacity )…
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 “tight regret”
New bounds on minimax regret for sequential probability assignment using logarithmic loss.
problem Minimizing regret in sequential probability assignment against arbitrary experts.
method Using self-concordance property of logarithmic loss to derive tight bounds.
result Tight bounds on minimax regret for various expert classes.
New study on regret lower bounds for multi-agent multi-armed bandit problems.
problem Understanding the limits of performance in multi-agent multi-armed bandit problems.
method Comprehensive study on different settings, establishing tight lower bounds.
result First comprehensive study on regret lower bounds across various settings.
The paper tightens the regret rate for linear bandit problems.
problem Bayesian regret in linear bandit problems.
method Information-theoretic framework and chaining argument.
result Established a new bound with a tight rate of .
Paper shows how online betting algorithms' regret can be used to create tight confidence sequences.
problem Estimating the expectation of random variables from samples and creating time-uniform confidence sequences.
method Converts the regret guarantee of universal portfolio algorithms into time-uniform concentration inequalities and confidence sequences.
result Numerically obtained confidence sequences are never vacuous and satisfy the law of iterated logarithm.
Improved single-pass streaming MAB regret bound to O(K^1/3T^2/3).
problem Minimize regret in single-pass streaming multi-armed bandits with sublinear memory.
method Improved regret lower bound to Ω(K^1/3T^2/3) and upper bound to O(K^1/3T^2/3).
result Achieved tight regret bound of O(K^1/3T^2/3) for algorithms with o(K) memory.
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…
Study analyzes broker's gain from trade in repeated context-based trading.
problem Maximizing traders' net utility in repeated context-based brokerage.
method Proposes algorithms achieving tight regret bounds in full and limited feedback settings.
result Achieves tight 1/2-approximation result for gain from trade.
We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the adaptively chosen observations are corrupted by Gaussian noise. We show that as the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as $Ω(σ\sqrt{T / \log (T)}) \cap …
Research aims to improve confidence intervals for RKHS elements in online learning.
problem Improper confidence intervals lead to suboptimal regret bounds in kernel-based bandit and reinforcement learning.
method Formalizes the open problem of online confidence intervals in RKHS and reviews existing results.
result Identifies the online nature of observation points as the main challenge for tight confidence intervals.
Optimizing rewards under budget constraints with correlated costs and rewards.
problem Maximizing total expected reward under a budget constraint on total cost with correlated and potentially heavy-tailed cost-reward pairs.
method Proposes algorithms exploiting correlation between cost and reward via linear minimum mean-square error estimation to achieve tight regret bounds.
result Achieves regret for a budget under certain moment conditions.
Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Banditscs.LG
New algorithms minimize regret in streaming MAB with memory constraints.
problem Minimizing regret in single-pass streaming MAB with limited memory.
method Developed two algorithms with tight regret bounds for different memory sizes.
result Established tight gap-dependent regret bounds for streaming MAB.
A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we close the problem of computationally and sample effi…
We study the regret minimization problem in the novel setting of generalized kernelized bandits (GKBs), where we optimize an unknown function belonging to a reproducing kernel Hilbert space (RKHS) having access to samples generated by an exponential family (EF) reward model whose mean is a non-linear function $μ(…
We consider recommendation systems that need to operate under wireless bandwidth constraints, measured as number of broadcast transmissions, and demonstrate a (tight for some instances) tradeoff between regret and bandwidth for two scenarios: the case of multi-armed bandit with context, and the case where there is a la…
Study finds optimal regret bound for multi-armed bandit problem with expert advice.
problem Optimizing decision-making in a multi-armed bandit problem with expert advice.
method Proved a tight lower bound matching the upper bound of Kale (2014) for minimax expected regret.
result The minimax optimal expected regret is Θ(√(T K log (N/K))) for the problem.
Balances the regret of different algorithms in bandit and RL problems.
problem Model selection in bandit and reinforcement learning.
method Estimates and balances the empirical regrets of algorithms.
result Achieves near-optimal regret compared to the optimal base algorithm.
State-of-the-art efficient model-based Reinforcement Learning (RL) algorithms typically act by iteratively solving empirical models, i.e., by performing \emph{full-planning} on Markov Decision Processes (MDPs) built by the gathered experience. In this paper, we focus on model-based RL in the finite-state finite-horizon…
We study the -armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. We introduce a tight asymptotic regret lower bound that is based on the information divergence. An algorithm that is inspired by the Deterministic…
The paper shows optimal robustness against adversarial corruption in sequential decision-making problems.
problem Optimal robustness to adversarial corruption in online decision-making problems.
method Investigates prediction with expert advice and multi-armed bandit problems, focusing on algorithms with decreasing learning rates and second-order regret bounds.
result Optimal robustness can be expressed by a square-root dependency on the amount of corruption, achieving -regret.
New lower bounds for combinatorial multi-armed bandits for general reward functions.
problem Maximizing reward in sequential decisions with sets of arms.
method Proved tight regret lower bounds for all smooth reward functions under mild assumptions.
result Lower bounds are tight up to log-factors for monotone reward functions.
New algorithms balance collaboration and adversarial behavior in linear bandits.
problem Minimizing regret in a collaborative linear bandit problem with adversarial agents.
method Robust collaborative phased elimination algorithm with tight analyses.
result Achieves near-optimal regret bounds of $O\left(α+ 1/\sqrt{M}
ight) \sqrt{dT}$ for good agents.
We consider the problem of Bayesian optimization (BO) in one dimension, under a Gaussian process prior and Gaussian sampling noise. We provide a theoretical analysis showing that, under fairly mild technical assumptions on the kernel, the best possible cumulative regret up to time behaves as and $O(\s…
Study tackles infinitely many-armed bandits with rotting rewards, achieving tight regret bounds.
problem Infinitely many-armed bandits with rotting rewards.
method Adaptive sliding window UCB algorithm for slow and abrupt rotting scenarios.
result Achieves tight regret bounds for both slow and abrupt rotting scenarios.
Paper solves no-swap regret minimization for combinatorial bandits with polylogarithmic dependence on N.
problem Design efficient no-swap regret algorithms for combinatorial bandits with exponentially large action space.
method Introduces a no-swap-regret learning algorithm with polylogarithmic dependence on N and demonstrates efficient implementation.
result Achieves no-swap regret with polylogarithmic dependence on N, resolving an open problem.
New algorithm minimizes Bayesian regret in offline linear bandits.
problem Minimizing Bayesian regret in offline linear bandits.
method Proposes a new algorithm that directly minimizes upper bounds on Bayesian regret using conic optimization.
result Upper bounds are tight and guarantee superior performance compared to LCB.
We provide new lower bounds on the regret that must be suffered by adversarial bandit algorithms. The new results show that recent upper bounds that either (a) hold with high-probability or (b) depend on the total lossof the best arm or (c) depend on the quadratic variation of the losses, are close to tight. Besides th…
Noiseless IO bounds inferred from demonstrations, matching adversarial settings.
problem Inferring decision-maker's objective from observed data.
method High-probability generalization bounds for induced action set.
result Generalization bound of for consistent estimators.
Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved regret with oracle queries for worst-case linear rewards.
New algorithm reduces control error in systems with changing dynamics.
problem Online control of systems with time-varying linear dynamics.
method Introduces adaptive regret metric and a novel meta-algorithm.
result First adaptive regret bound for online convex optimization with memory.
New insights link no-regret learning to online conformal prediction in adversarial settings.
problem Understanding the relationship between no-regret learning and online conformal prediction in adversarial environments.
method Analysis of existing algorithms and new connections between no-regret learning and conformal prediction.
result No-regret learning algorithms can provide group-conditional coverage guarantees in adversarial settings.
Optimizes quantile and semi-adversarial regret with novel root-logarithmic regularizers.
problem Minimizes regret in adversarial and semi-adversarial online learning.
method FTRL with root-logarithmic regularizers for quantile and semi-adversarial settings.
result Achieves minimax optimal regret bounds in both paradigms.
A collaborative algorithm reduces regret in federated linear contextual bandits.
problem Optimizing decision-making in federated learning with heterogeneous data.
method Fed-PE algorithm, leveraging geometric structure of rewards, multi-client G-optimal design.
result Achieves near-optimal regrets with logarithmic communication costs.
We study the control of a linear dynamical system with adversarial disturbances (as opposed to statistical noise). The objective we consider is one of regret: we desire an online control procedure that can do nearly as well as that of a procedure that has full knowledge of the disturbances in hindsight. Our main result…
Improved statistical efficiency of Thompson Sampling for combinatorial semi-bandits.
problem Efficiency of policies in stochastic combinatorial multi-armed bandits with semi-bandit feedback.
method Analysis of Combinatorial Thompson Sampling (CTS) using Beta and Gaussian priors for mutually independent and multivariate sub-Gaussian outcomes.
result CTS provides an efficient policy with optimal asymptotic regret for both mutually independent and multivariate sub-Gaussian outcomes.
Improves policy optimization with polylog(T) regret bounds for stochastic losses.
problem Improves theoretical guarantees for policy optimization in stochastic settings.
method Leverages Tsallis and Shannon entropy regularizers for polylog(T) regret, and log-barrier regularizer for adversarial settings.
result Achieves a first-order polylog(T) regret bound for policy optimization in stochastic settings.
Motivated by economic applications such as recommender systems, we study the behavior of stochastic bandits algorithms under \emph{strategic behavior} conducted by rational actors, i.e., the arms. Each arm is a \emph{self-interested} strategic player who can modify its own reward whenever pulled, subject to a cross-per…
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…
New algorithm reduces online learning regret for bounded recall games.
problem Reducing regret in online learning with limited past information.
method Constructing a stationary bounded-recall algorithm with regret.
result Any low regret bounded-recall algorithm must be aware of past losses' order.
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.
New method uses correlated auxiliary feedback to reduce regret in parameterized bandits.
problem Reducing regret in parameterized bandits with correlated auxiliary feedback.
method Develops a reward estimator using auxiliary feedback with tight confidence bounds.
result Shows significant reduction in regret compared to standard methods.
New bounds for -regret using modified Decision-Estimation Coefficient.
problem Statistical characterization of -regret for complex bandit problems.
method Statistical characterization via -DEC, a modified Decision-Estimation Coefficient.
result Upper and lower bounds for -regret nearly match, showing fundamental limits.
New algorithm reduces adaptive regret without projections.
problem Computational expense of projections in online convex optimization.
method Lazy gradient-based algorithm with set-membership computations.
result Near-optimal adaptive regret bounds for general convex functions.
Optimistic Hedge achieves optimal regret bounds in two-player zero-sum games.
problem Achieving optimal regret bounds for optimistic Hedge in two-player zero-sum games.
method Refined regret analysis and optimization problem formulation.
result Optimistic Hedge achieves regret bounds, matching upper and lower bounds.
Study on a new family of problems interpolating expert advice and multi-armed bandits.
problem A new family of problems combining expert advice and multi-armed bandits.
method Proved minimax regret bounds and designed optimal PAC algorithms for pure exploration.
result Tight minimax regret bounds and optimal PAC algorithm for -BAI.
We consider combinatorial online learning with subset choices when only relative feedback information from subsets is available, instead of bandit or semi-bandit feedback which is absolute. Specifically, we study two regret minimisation problems over subsets of a finite ground set , with subset-wise relative prefe…
New algorithm reduces memory-regret trade-off for bandits.
problem Optimizing memory usage in stochastic multi-armed bandits.
method Designing an algorithm with specific regret bound and proving lower bound.
result Optimal regret characterization in terms of memory and rounds.
Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Banditsstat.ML
New Thompson sampling algorithm reduces regret for exponential family bandits.
problem Minimizing regret in multi-armed bandit problems with exponential family rewards.
method Proposes ExpTS and ExpTS algorithms using novel sampling distributions.
result Minimizes both finite-time and asymptotic regret for exponential family rewards.