Regret minimization is treated as the golden rule in the traditional study of online learning. However, regret minimization algorithms tend to converge to the static optimum, thus being suboptimal for changing environments. To address this limitation, new performance measures, including dynamic regret and adaptive regr…
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 “minimal regret”
Regret minimization is a powerful tool for solving large-scale problems; it was recently used in breakthrough results for large-scale extensive-form game solving. This was achieved by composing simplex regret minimizers into an overall regret-minimization framework for extensive-form game strategy spaces. In this paper…
Algorithm minimizes regret and converges to equilibria in Markov games.
problem Regret minimization and convergence to equilibria in general-sum Markov games under adversarial opponents.
method Decentralized algorithm that uses policy optimization and controls path length to achieve sublinear regret.
result Sublinear regret guarantees for convergence to correlated equilibrium in Markov games.
We consider regret minimization in repeated games with non-convex loss functions. Minimizing the standard notion of regret is computationally intractable. Thus, we define a natural notion of regret which permits efficient optimization and generalizes offline guarantees for convergence to an approximate local optimum. W…
The paper tackles best arm identification with minimal regret in experiments.
problem Identifying the best arm with minimal regret in experiments.
method Information-theoretic techniques and Double KL-UCB algorithm.
result Achieves asymptotic optimality in identifying the best arm with minimal regret.
New algorithms minimize simple and cumulative regret in contextual bandits.
problem Minimizing simple and cumulative regret in contextual bandit settings.
method Proposed new algorithms using conformal arm sets (CASs).
result Near-optimal minimax guarantees for simple regret and state-of-the-art guarantees for cumulative regret.
There are two variants of the classical multi-armed bandit (MAB) problem that have received considerable attention from machine learning researchers in recent years: contextual bandits and simple regret minimization. Contextual bandits are a sub-class of MABs where, at every time step, the learner has access to side in…
New algorithm minimizes worst-case regret in uncertain, time-varying dynamics.
problem Model-based policy learning in uncertain, time-varying dynamics.
method Planning regret metric and iterative algorithm for minimizing it.
result Empirical evidence shows the proposed algorithm outperforms existing methods.
The paper minimizes Borda regret in dueling bandits models.
problem Minimizing Borda regret in dueling bandits models.
method Proposes explore-then-commit and EXP3-type algorithms for stochastic and adversarial settings respectively.
result Achieves nearly matching regret upper bounds of for both settings.
This paper begins with a study on the dual representations of risk and regret measures and their impact on modeling multistage decision making under uncertainty. A relationship between risk envelopes and regret envelopes is established by using the Lagrangian duality theory. Such a relationship opens a door to a decomp…
Paper explores rate-preserving reductions between Blackwell approachability and no-regret learning.
problem Tackles rate-preserving reductions between Blackwell approachability and no-regret learning.
method Studies fine-grained reductions and optimal rates of convergence.
result Shows that rate-preserving reductions do not always hold, but provides conditions for when they do.
New online conformal prediction methods minimize strongly adaptive regret and achieve near-optimal coverage.
problem Uncertainty quantification in online settings with changing data distributions.
method Developed new online conformal prediction methods that minimize strongly adaptive regret.
result Achieve near-optimal strongly adaptive regret and approximately valid coverage.
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.
Dynamic regret minimization is shown equivalent to static regret minimization for linear losses.
problem Dynamic regret minimization in online convex optimization.
method Equivalence between dynamic and static regret minimization for linear losses.
result Dynamic regret minimization is equivalent to static regret minimization for linear losses.
New algorithm reduces regret by allowing free exploration in multi-armed bandits.
problem Designing an adaptive policy to minimize regret with a free exploration budget.
method Introduced -probably saving policies and a two-phase algorithm UFE-KLUCB-H.
result UFE-KLUCB-H accumulates strictly less regret than non-free exploration policies.
Protocol learns pure quantum states with minimal disturbance.
problem Efficiently learn quantum states with minimal disturbance.
method Sequential measurements with minimal disturbance.
result Achieves maximal precision with polylogarithmic regret.
The paper improves on existing algorithms for minimizing different types of regret in online learning.
problem Minimizing external, internal, and swap regret in online learning with multiple experts.
method Develops a single algorithm using φ-regret minimization and Haar-wavelet-inspired matrix features to achieve optimal bounds in various scenarios.
result Achieves optimal bounds for external, internal, and swap regrets in different expert scenarios.
New algorithm SELECT minimizes satisficing regret in bandits.
problem Minimizing regret in bandit optimization with satisficing arms.
method SELECT algorithm for satisficing regret minimization.
result SELECT achieves constant expected satisficing regret.
New algorithm learns FMDP structure while minimizing regret.
problem Regret minimization in FMDPs with unknown structure.
method Optimism in face of uncertainty principle combined with statistical structure learning.
result First algorithm to learn FMDP structure while minimizing regret.
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.
Competing With Strategiesstat.ML
We study the problem of online learning with a notion of regret defined with respect to a set of strategies. We develop tools for analyzing the minimax rates and for deriving regret-minimization algorithms in this scenario. While the standard methods for minimizing the usual notion of regret fail, through our analysis …
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 meta-learning framework for minimizing simple regret in bandits.
problem Minimizing simple regret in a sequence of bandit tasks with unknown distributions.
method Developed Bayesian and frequentist meta-learning algorithms for bandits, analyzing their meta simple regret.
result Bayesian algorithm achieves meta simple regret, frequentist algorithm .
New algorithm DUSA minimizes regret in structured bandits with structural information.
problem Optimal decision-making under uncertainty with structural reward information.
method DUSA algorithm exploiting convex structural information.
result Regret matches information-theoretic lower bound up to a constant factor.
Unified framework for best arm identification and dueling bandits regret minimization.
problem Best arm identification and dueling bandits regret minimization.
method Tree-Guided Identify-Then-Exploit (TG-ITE) framework.
result Unified approach achieving optimal sample complexity and regret guarantees.
Survey of universal portfolio techniques for minimizing investment regret.
problem Minimizing investment regret in algorithmic trading.
method Explains various universal portfolio techniques and their proofs.
result Coverage of fundamental concepts and algorithms in regret minimization.
Optimal algorithm for minimizing regret in heavy-tailed bandits.
problem Minimizing regret in stochastic multi-armed bandits with heavy-tailed distributions.
method Proposes an optimal algorithm under the assumption of uniformly bounded moments of order (1+ε).
result Matches the lower bound exactly in the first-order term and provides a finite-time bound on its regret.
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.
State of the art online learning procedures focus either on selecting the best alternative ("best arm identification") or on minimizing the cost (the "regret"). We merge these two objectives by providing the theoretical analysis of cost minimizing algorithms that are also delta-PAC (with a proven guaranteed bound on th…
New algorithm selects optimal subset for multiclass classifier training.
problem Selecting optimal subset of labeled examples for multiclass classifier training.
method Regret minimization framework with new regularization scheme.
result New method consistently outperforms state-of-the-art approaches.
Study shows nonstationary bandits require T-dependent regret even with minimal nonstationarity.
problem Understanding satisficing regret in nonstationary multi-armed bandits.
method Developed a novel Fano-based framework for nonstationary bandits with a post-interaction reference construction.
result Optimal regret scales with T even with minimal nonstationarity, contrasting with stationary case.
Algorithm minimizes regret in multi-criteria bandits with constraints.
problem Optimize primary attribute while respecting secondary constraints.
method Con-LCB algorithm that guarantees logarithmic regret and feasibility identification.
result Logarithmic regret and feasibility identification with high probability.
New bounds show polyhedral surrogates are optimal for generalization.
problem Proving generalization rates for polyhedral loss functions.
method Developed two general results for polyhedral surrogates.
result Polyhedral surrogates provide linear surrogate regret bounds, translating directly to target rates.
We consider online algorithms under both the competitive ratio criteria and the regret minimization one. Our main goal is to build a unified methodology that would be able to guarantee both criteria simultaneously. For a general class of online algorithms, namely any Metrical Task System (MTS), we show that one can sim…
New algorithm optimizes best arm identification with minimal regret.
problem Best arm identification in multi-armed bandit problems.
method Characterized Bayesian simple regret with continuity conditions of prior, proposed a simple algorithm.
result Proposed algorithm achieves rate-optimal Bayesian simple regret.
We consider online learning problems where the aim is to achieve regret which is efficient in the sense that it is the same order as the lowest regret amongst K experts. This is a substantially stronger requirement that achieving or regret with respect to the best expert and standard algorithm…
New algorithm reduces online logistic regression regret without exponential constant.
problem Improper learning in online logistic regression with logarithmic regret.
method Regularized empirical risk minimization with surrogate losses.
result Regret scaling as O(B log(Bn)) with low computational complexity.
A method to minimize regret in multi-agent control systems with adversarial disturbances.
problem Optimal control of dynamical systems with adversarial disturbances and multiple agents.
method Reduction from online convex optimization to a distributed algorithm for multi-agent control.
result The resulting distributed algorithm has low regret relative to the optimal precomputed joint policy.
Adaptive algorithms minimize regret in matching markets with contextual arm preferences.
problem Minimizing regret in matching markets with context-dependent player utilities.
method Developed adaptive algorithms for stochastic and adversarial contexts, providing upper and lower bounds.
result Achieved sublinear regret bounds for both stochastic and adversarial contexts.
We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over jo…
We study the problem of regret minimization in partially observable linear quadratic control systems when the model dynamics are unknown a priori. We propose ExpCommit, an explore-then-commit algorithm that learns the model Markov parameters and then follows the principle of optimism in the face of uncertainty to desig…
Bandit algorithms struggle with consistent performance and robustness.
problem Achieving consistent and robust performance in stochastic multi-armed bandit settings.
method Analyzing regret minimization trade-offs and proposing distribution-oblivious algorithms.
result Logarithmic regret is inconsistent and super-logarithmic regret is necessary for consistent learning.
New algorithm reduces regret by focusing on near-optimal actions.
problem Regret minimization in multi-armed bandits leads to over-exploitation.
method Proposes a lenient regret criterion and a new algorithm, ε-TS.
result ε-TS achieves asymptotic optimality in lenient regret.
This work improves regret minimization for logistic bandits by reducing dependence on a large constant.
problem Minimizing regret in logistic bandits with reduced dependence on a large constant.
method Experimental design procedure and warmup sampling algorithm.
result Achieves a minimax regret of \(O(\sqrt{d \dotμT\log(|\mathcal{X}|)})\) in the fixed arm setting.
Most bandit algorithm designs are purely theoretical. Therefore, they have strong regret guarantees, but also are often too conservative in practice. In this work, we pioneer the idea of algorithm design by minimizing the empirical Bayes regret, the average regret over problem instances sampled from a known distributio…
New method minimizes regret in AMDP with high probability.
problem Pessimistic regret analysis in AMDP.
method Developed a new policy search method achieving optimistic regret.
result Achieved sublinear optimistic regret with high probability.
Algorithm minimizes regret in non-stationary dueling bandits with unknown parameters.
problem Minimizing regret in dueling bandits with time-varying preferences.
method Proposes Beat the Winner Reset algorithm and meta-algorithms DETECT and Monitored Dueling Bandits.
result Proves bounds on expected weak and strong regret for non-stationary dueling bandits.
Paper addresses regret minimization and inference in high-dimensional online decision-making.
problem Regret minimization and statistical inference in high-dimensional online decision-making.
method Integrates ε-greedy bandit algorithm with hard thresholding for sparse bandit parameters and debiasing method for inference.
result Achieves either regret or -consistent inference, with trade-off between exploration and exploitation.