I analyse the frequentist regret of the famous Gittins index strategy for multi-armed bandits with Gaussian noise and a finite horizon. Remarkably it turns out that this approach leads to finite-time regret guarantees comparable to those available for the popular UCB algorithm. Along the way I derive finite-time bounds…
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 “finite regret”
FP-UCB algorithm achieves bounded regret for finitely parameterized multi-armed bandits.
problem Finitely parameterized multi-armed bandits with unknown but known parameter set.
method FP-UCB algorithm using structural information about the parameter set.
result FP-UCB achieves bounded regret under structural condition, logarithmic otherwise.
I introduce and analyse an anytime version of the Optimally Confident UCB (OCUCB) algorithm designed for minimising the cumulative regret in finite-armed stochastic bandits with subgaussian noise. The new algorithm is simple, intuitive (in hindsight) and comes with the strongest finite-time regret guarantees for a hori…
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.
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.
We present a new anytime algorithm that achieves near-optimal regret for any instance of finite stochastic partial monitoring. In particular, the new algorithm achieves the minimax regret, within logarithmic factors, for both "easy" and "hard" problems. For easy problems, it additionally achieves logarithmic individual…
Logarithmic regret achieved in continuous-time linear-quadratic reinforcement learning.
problem Optimizing control actions in unknown continuous-time systems over a finite time horizon.
method Least-squares algorithm based on continuous-time observations and controls, with perturbation analysis and parameter estimation error analysis.
result Logarithmic regret bound of order .
Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcs.LG
New algorithms minimize regret in SSP with optimal sparse updates.
problem Minimizing regret in Stochastic Shortest Path models.
method Implicit finite-horizon approximation for analysis, model-free and model-based algorithms developed.
result Minimax optimal regret for both model-free and model-based algorithms.
Paper improves worst-case regret bounds for RLSVI in reinforcement learning.
problem Minimizing regret in reinforcement learning with randomized value functions.
method Introduces a clipping variant of Thompson Sampling for RLSVI.
result Achieves a worst-case regret bound.
New method for semiparametric bandits reduces regret to optimal levels.
problem Complex reward structures in semiparametric bandits.
method Experimental-design approach with sharp regret bound and PAC bound.
result Minimax regret of and logarithmic regret under positive suboptimality gap.
New algorithm for countable bandits with optimal regret.
problem Stochastic bandit problem with countably many arms.
method Fully adaptive online learning algorithm with O(log n) expected cumulative regret.
result Achieves optimal regret of O(log n) after any number of plays n.
Meta-learning control algorithm with finite-time guarantees for unknown systems.
problem Online control of unknown linear systems with constraints.
method Provable regret guarantees for an iterative control algorithm.
result Regret bounds of for controller cost and constraint violation.
New algorithm optimizes beam and rate allocation in mmWave systems for multiple users.
problem Optimizing beam and rate allocation in mmWave systems for multiple users with limited feedback.
method Introducing SAT-CTS, a combinatorial semi-bandit policy with satisficing objective.
result SAT-CTS achieves finite-time regret bounds and reduces satisficing regret in mmWave systems.
New algorithm CROP achieves asymptotic optimality with bounded regret.
problem Optimistic algorithms fail to achieve asymptotic instance-dependent regret optimality.
method CRush Optimism with Pessimism (CROP) algorithm that eliminates optimistic hypotheses.
result CROP achieves constant-factor asymptotic optimality and bounded regret.
This paper improves Thompson Sampling for complex decision-making problems.
problem Learning in infinite-horizon discounted decision processes with unknown parameters.
method Developed a general canonical probability space and new metrics for analyzing adaptive learning algorithms.
result Thompson Sampling achieves complete learning in complex decision-making problems.
UCB-Advantage learns MDPs with regret.
problem Model-free reinforcement learning in finite-horizon MDPs.
method Reference-Advantage decomposition for low regret.
result Achieves regret, matching best known bounds.
Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescs.LG
New algorithm reduces regret in CMDPs without cancellation of errors.
problem Lagrangian approaches in CMDPs struggle with cancellation of errors.
method OptAug-CMDP, based on augmented Lagrangian method.
result Regret of for both objective and constraint violation.
Partial monitoring is a general model for sequential learning with limited feedback formalized as a game between two players. In this game, the learner chooses an action and at the same time the opponent chooses an outcome, then the learner suffers a loss and receives a feedback signal. The goal of the learner is to mi…
New framework analyzes regret in guided diffusion for optimizing structured inputs.
problem Understanding regret behavior in guided-diffusion black-box optimization for structured design problems.
method Developed a certificate-based expected simple-regret framework that avoids assumptions breaking down in modern diffusion BO pipelines.
result Explains how exponential and polynomial convergence can arise from mass lift in near-optimal designs.
We present an algorithm based on the \emph{Optimism in the Face of Uncertainty} (OFU) principle which is able to learn Reinforcement Learning (RL) modeled by Markov decision process (MDP) with finite state-action space efficiently. By evaluating the state-pair difference of the optimal bias function , the propos…
Unified proof for various bandit algorithms with logarithmic regret.
problem Achieving logarithmic regret in stochastic bandit algorithms.
method Minimal high-probability concentration condition and two deterministic lemmas.
result Unified proofs for classical and contemporary bandit algorithms.
RANDomized-exploration policy Optimization via Multiple Importance Sampling with Truncation (RANDOMIST) for PO with mediator feedback.
problem Policy Optimization in continuous control tasks.
method RANDomized-exploration policy Optimization via Multiple Importance Sampling with Truncation (RANDOMIST) for regret minimization in PO.
result Achieving constant regret under certain circumstances in PO with mediator feedback.
Improved regret bounds for linear bandits with heavy-tailed rewards.
problem Stochastic linear bandits with heavy-tailed rewards.
method Elimination-based algorithm guided by experimental design.
result Regret bound of \(\tilde{\mathcal{O}}(d^\frac{1+3ε}{2(1+ε)} T^\frac{1}{1+ε})\) for \(ε\in (0,1)\).
Optimizing Regretecon.EM
The paper optimizes regret using covariance between costs and decisions.
problem Optimizing expected regret in decision-making problems.
method Developed derivative theory of covariance regret functional, derived Gâteaux derivative, and extended to constrained optimization.
result Gradient of covariance regret is the cost covariance matrix, with implications for portfolio optimization.
We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the adversary. We then generalise the information-theoretic tools of Russo and Van Roy (2016) for proving Bayesian regret bounds and combine th…
New algorithms reduce regret in online convex optimization with heavy-tailed gradients.
problem Challenges in online convex optimization with heavy-tailed gradients.
method Examined and analyzed old algorithms for online convex optimization in the heavy-tailed setting.
result Established new regret bounds for classical methods without algorithmic modification.
We tackle the problem of online reward maximisation over a large finite set of actions described by their contexts. We focus on the case when the number of actions is too big to sample all of them even once. However we assume that we have access to the similarities between actions' contexts and that the expected reward…
We study online reinforcement learning for finite-horizon deterministic control systems with {\it arbitrary} state and action spaces. Suppose that the transition dynamics and reward function is unknown, but the state and action space is endowed with a metric that characterizes the proximity between different states and…
Agents collaborate to reduce regret in a multi-agent linear bandit problem with side information.
problem Reducing regret in a multi-agent stochastic linear bandit with side information.
method A decentralized algorithm where agents communicate subspace indices and each plays a projected LinUCB on the corresponding low-dimensional subspace.
result Per-agent finite-time regret is much smaller when agents communicate compared to non-communicating case.
Kernel-UCBVI algorithm balances exploration and exploitation in metric state-action spaces.
problem Exploration-exploitation dilemma in finite-horizon reinforcement learning with metric state-action spaces.
method Kernel-UCBVI, leveraging smoothness and kernel estimators of rewards and transitions.
result First regret bound for kernel-based RL using smoothing kernels, .
Optimal scheme minimizes deviation in federated transfer learning for kernel regression.
problem Minimizing cumulative deviation in federated transfer learning across multiple datasets.
method Regret-optimal iterative scheme for continual communication between nodes and server.
result Explicit updates for the regret-optimal algorithm in finite-rank kernel regression.
New RL algorithm reduces regret in finite-horizon episodic tasks.
problem Minimizing regret in model-based reinforcement learning.
method Optimism principle applied to value-targeted regression.
result Regret bound of for linear mixtures.
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.
Logarithmic regret for continuous-time reinforcement learning.
problem Continuous-time Markov decision processes with unknown transition probabilities and holding times.
method Upper confidence reinforcement learning, mean holding time estimation, stochastic comparison of point processes.
result Logarithmic regret bound achieved in finite time.
Optimal algorithm found for collaborative learning in bandits with optimal regret bounds.
problem Minimizing regret in collaborative multi-agent bandit problems.
method Proposed an algorithm with optimal regret bounds for collaborative multi-agent multi-armed bandit model.
result First algorithm with order optimal regret bounds for collaborative bandit model.
New algorithm reduces online learning error for unknown feature distributions.
problem Oracle-efficient hybrid online learning with unknown feature and label distributions.
method Computational efficient online predictor using ERM oracle for finite-VC and fat-shattering classes.
result Oracle-efficient sublinear regret bounds for hybrid online learning with unknown feature generation.
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradoxstat.ML
Thompson Sampling shows polynomial regret for combinatorial semi-bandits with subgaussian rewards.
problem Finding optimal solutions in combinatorial semi-bandits with suboptimal sampling.
method Proposes Thompson Sampling with polynomial regret for linear combinatorial semi-bandits.
result Demonstrates 'mismatched sampling paradox' where knowing distributions can lead to worse performance.
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.
Adaptive-treed banditsmath.ST
We describe a novel algorithm for noisy global optimisation and continuum-armed bandits, with good convergence properties over any continuous reward function having finitely many polynomial maxima. Over such functions, our algorithm achieves square-root regret in bandits, and inverse-square-root error in optimisation, …
In this paper, we consider the problem of predicting observations generated online by an unknown, partially observed linear system, which is driven by stochastic noise. For such systems the optimal predictor in the mean square sense is the celebrated Kalman filter, which can be explicitly computed when the system model…
New bounds for adaptive control in high dimensions without fixed state space.
problem Adaptive control of linear systems in high or infinite dimensions.
method Novel perturbation bound for certainty equivalence, scaling with prediction error.
result First regret bounds for LQR in infinite dimensional systems, independent of ambient dimension.
New framework calibrates decision robustness using inverse conformal risk control.
problem Inadequate robustness levels in decision-making due to ad hoc choices.
method Constructs valid estimators to trace miscoverage-regret Pareto frontier.
result Provides distribution-free, finite-sample guarantees on robustness levels.
Study risk-sensitive reinforcement learning with Lipschitz dynamic risk measures, establishing regret bounds.
problem Risk-sensitive reinforcement learning in Markov decision processes.
method Two model-based algorithms for Lipschitz dynamic risk measures, focusing on regret bounds.
result Upper bounds demonstrate optimal dependencies on actions and episodes, reflecting risk sensitivity vs. sample complexity trade-off.
This paper improves online learning algorithms for LP problems, achieving better regret bounds.
problem Achieving optimal regret bounds in online linear programming.
method Develops a new framework for first-order online learning algorithms under certain error bound conditions.
result First-order learning algorithms achieve regret in continuous support and regret in finite support, improving over .
Kernel -Greedy optimizes multi-armed bandits with covariates for sub-linear regret.
problem Optimizing multi-armed bandits with covariates in a reproducing kernel Hilbert space.
method Online weighted kernel ridge regression estimator for mean reward function estimation.
result Achieves sub-linear regret rate and optimal regret rate under margin condition.
A new metric, Weighted Regret, unifies FDR and power evaluation in online multiple testing.
problem The asymmetric costs of false positives and false negatives in automated pipelines.
method Introducing Weighted Regret and Decoupled-OMT (DOMT) to unify FDR and power evaluation.
result DOMT achieves an order-optimal sublinear mitigation of threshold depletion in bursty environments.
New bounds on IDS for RL show how to balance computation and learning efficiency.
problem Understanding and optimizing information-directed sampling (IDS) for reinforcement learning.
method Developed novel information-theoretic tools to bound information ratio and cumulative information gain.
result Derived prior-free Bayesian regret bounds for IDS in tabular finite-horizon MDPs and improved computational efficiency.
Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizescs.LG
Avare improves optimization and sampling with adaptive importance sampling.
problem Improving convergence rate of stochastic gradient-based algorithms.
method Adaptive importance sampling with decreasing step-sizes.
result Achieves dynamic regret bounds of and .