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…
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 “minimax 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.
We develop a new theoretical framework, the \emph{envelope complexity}, to analyze the minimax regret with logarithmic loss functions and derive a Bayesian predictor that adaptively achieves the minimax regret over high-dimensional -balls within a factor of two. The prior is newly derived for achieving the mini…
New adaptive learning rate for FTRL reduces regret to Θ(T^2/3).
problem Minimax regret of Θ(T^2/3) in online learning.
method Adaptive learning rate framework matching stability, penalty, and bias terms.
result Improves Best-of-Both-Worlds (BOBW) regret upper bounds.
New algorithm reduces worst-case regret for heavy-tailed bandits.
problem Stochastic Multi-Armed Bandit problem with heavy-tailed rewards.
method Modified minimax policy MOSS with saturated empirical mean.
result Worst-case regret matching lower bound for heavy-tailed distributions.
Study minimax regret in sequential probability assignment with and without side information.
problem Minimax regret analysis in sequential probability assignment.
method Upper and lower bounds on minimax regret using square-root entropy.
result Lower bound matches upper bound for Donsker classes, up to log factors.
We study the problem of switching-constrained online convex optimization (OCO), where the player has a limited number of opportunities to change her action. While the discrete analog of this online learning task has been studied extensively, previous work in the continuous setting has neither established the minimax ra…
The paper tackles minimax optimality in continuum contextual bandits with Hölder continuity.
problem Minimizing regret in a continuum of contexts with Hölder continuity.
method Proves a static-to-contextual regret conversion theorem and analyzes various dependency cases.
result Achieves minimax optimal contextual regret for convex and strongly convex bandits.
New method for sequential probability assignment reduces regret using contextual Shtarkov sums.
problem Minimizing regret in sequential probability assignment with arbitrary hypothesis classes.
method Introducing contextual Shtarkov sum and contextual Normalized Maximum Likelihood (cNML) algorithm.
result The contextual Shtarkov sum characterizes minimax regret and provides a minimax optimal strategy.
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.
The paper optimizes risk-sensitive RL with CVaR, achieving near-minimax-optimal results.
problem Optimizing risk-sensitive reinforcement learning with CVaR objective.
method Developed algorithms for multi-arm bandits and online RL in MDPs, achieving near-minimax-optimal regret.
result Achieved near-minimax-optimal regret of for constant .
Efficient algorithm for global optimization of multivariate Lipschitz functions.
problem Global optimization of multivariate Lipschitz continuous functions.
method Proposes an efficient minimax optimal algorithm using a predetermined query creation rule.
result Achieves an average regret bound of , minimax optimal.
Study minimax optimal RL in factored MDPs with bonus exploration.
problem Optimal reinforcement learning in episodic factored MDPs.
method Proposes two model-based algorithms with bonus exploration for minimax optimal regret.
result Achieves minimax optimal regret guarantees for rich factored structures.
GP-UCB performs suboptimally under certain conditions, as shown by a new regret lower bound.
problem The suboptimality of GP-UCB under polynomial effective optimism.
method Analysis of effective optimism level and new regret lower bound.
result GP-UCB is not minimax optimal under polynomial growth of effective optimism.
Paper characterizes minimax regret rates for online ranking with top-k feedback.
problem Analyzing online ranking with partial feedback.
method Developed techniques from partial monitoring to characterize minimax regret rates.
result Full characterization of minimax regret rates for Precision@n.
The paper tackles robust policy learning from multiple data sources.
problem Learning a policy that generalizes across diverse settings from multiple heterogeneous data sources.
method Proposes a minimax regret optimization objective and a policy learning algorithm combining doubly robust offline policy evaluation and no-regret learning.
result Achieves minimal worst-case mixture regret up to a moderated vanishing rate of the total data across all sources.
Paper finds algorithms with both low regret and high exploitation.
problem Finding algorithms with both low regret and high exploitation.
method Investigates online learning algorithms with bandit feedback.
result First affirmative answer to guaranteeing both regret and regret.
New algorithm reduces bandit regret to log^3(T).
problem Noise model for linear stochastic bandits with vanishing noise.
method Weighted least-squares estimation, leveraging eigenvalue relation.
result Minimax regret scaling as log^3(T) for time horizon T.
New algorithm achieves optimal regret in average reward MDPs without prior bias information.
problem Achieving optimal regret in average reward MDPs with computational efficiency and without prior bias information.
method Projective Mitigated Extended Value Iteration (PMEVI) to compute bias-constrained optimal policies efficiently.
result First tractable algorithm with minimax optimal regret of .
Optimal algorithm for identifying best-arm with minimal regret.
problem Identifying the best arm in two treatments with limited budget.
method Neyman allocation based on outcome standard deviations.
result Neyman allocation is minimax optimal for simple regret.
Study minimax regret in bilateral trade with heavy-tailed valuations.
problem Minimizing regret in bilateral trade with infinite variance valuations.
method Extended self-bounding property, truncated-mean estimation, epoch-based algorithm.
result Achieves regret bound of under specific conditions.
MOTS improves Thompson sampling to match minimax bounds for bandit problems.
problem Achieving optimal regret bounds for Thompson sampling in multi-armed bandit problems.
method Proposes MOTS, a variant of Thompson sampling that clips arm sampling.
result Proves MOTS achieves minimax optimal regret bounds .
E algorithm optimizes batched linear bandits with minimal regret and batches.
problem Optimizing batched linear bandits for minimal regret.
method Explore-Estimate-Eliminate-Exploit framework with optimal exploration rate.
result Achieves minimax and asymptotic optimality in regret and batch complexity.
Proposes MRO to achieve uniformly low regret in distributionally robust learning.
problem Learning under unknown test distributions (distribution shift).
method Minimax Regret Optimization (MRO) for robust machine learning.
result MRO achieves uniformly low regret across all test distributions.
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…
Optimal algorithm for high-dimensional stochastic linear bandits with sparse parameters.
problem High-dimensional stochastic linear bandits with sparse parameters.
method Three-stage arm selection algorithm using thresholded Lasso for estimation.
result Achieves exact minimax optimality in cumulative regret.
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.
Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, accuracy.
Optimal algorithm for linear bandits on ellipsoids with minimax regret bound.
problem Linear stochastic bandits on ellipsoids.
method Novel sequential procedure to estimate norm of parameters, followed by an explore-and-commit strategy.
result Regret bound matches minimax lower bound with multiplicative constant.
Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularizationstat.ML
Adapting Hedge algorithm for semi-adversarial data with root-entropy regularization.
problem Minimizing regret in prediction with expert advice under varying distributions.
method Follow-the-Regularized-Leader (FTRL) with root-entropy regularization.
result Adaptive minimax optimal regret across all levels of constraint sets.
New algorithm reduces regret for kernelized bandits by adapting to specific problem instances.
problem Efficiently learning the optimizer of an unknown function in RKHS with noisy oracle.
method Instance-dependent regret analysis and a new minimax near-optimal algorithm.
result New algorithm achieves better performance on specific problem instances.
Paper analyzes nonconvex bandit problems with improved adaptive methods.
problem Continuous armed bandit problems for nonconvex cost functions.
method Simple and adaptive bin splitting methods.
result Adaptive method achieves locally minimax optimal expected cumulative regret.
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 algorithm adapts to unknown demand smoothness for dynamic pricing.
problem Dynamic pricing with unknown Hölder smoothness of demand function.
method Self-similarity condition and adaptive algorithm.
result Adaptive algorithm achieves minimax optimal regret without prior knowledge of smoothness.
New algorithms minimize regret in multi-task and lifelong linear bandits with shared representation.
problem Minimizing regret in multi-task and lifelong linear bandits with shared representation.
method Novel algorithms using efficient estimator for low-rank linear feature extractor and novel analysis.
result Achieved regret bounds matching minimax lower bound up to logarithmic factors.
UCBVI-γ algorithm minimizes regret in discounted MDPs.
problem Minimizing regret in discounted MDPs.
method Optimism in the face of uncertainty principle and Bernstein-type bonus.
result UCBVI-γ achieves nearly minimax optimal regret.
Study online learning with delays and capacity constraints, achieving optimal regret bounds.
problem Online learning with delays and capacity constraints.
method Novel scheduling and preemptive techniques, matching upper and lower bounds.
result Achieves optimal regret bounds across all capacity levels.
The paper identifies network bottlenecks using minimax paths in stochastic networks.
problem Identifying bottlenecks in networks with stochastic weights.
method Modeling as combinatorial semi-bandit problem, applying combinatorial Thompson Sampling, and approximating the original objective due to computational intractability.
result Established an upper bound on Bayesian regret and evaluated Thompson Sampling performance on real-world networks.
This paper studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
problem Optimizing an unknown function with limited evaluations.
method Studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
result Minimax rates over Besov spaces are identical to those over the smallest Hölder space into which Besov spaces embed.
The paper studies how arm selection in a bandit problem changes with shape constraints.
problem Stochastic Thresholding Bandit Problem under shape constraints.
method Investigation of TBP under four shape constraints: monotonic increasing, unimodal, concave, and fixed.
result Minimax rates for regret vary significantly depending on the shape constraint.
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.
We prove non-asymptotic lower bounds on the expectation of the maximum of independent Gaussian variables and the expectation of the maximum of independent symmetric random walks. Both lower bounds recover the optimal leading constant in the limit. A simple application of the lower bound for random walks is an (…
Optimal adaptive experiment for choosing best treatment with binary outcomes.
problem Choosing the best treatment from binary options in an adaptive experiment.
method Adaptive experiment with two phases: treatment allocation and choice. Neyman allocation method used.
result Neyman allocation is minimax and Bayes optimal, matching lower bounds for regret.
New algorithm for non-stationary bandits with slow drifts.
problem Minimizing dynamic regret in non-stationary bandits with slowly varying rewards.
method Extends Successive Elimination to non-stationary bandits with a novel gap profile characterization.
result First instance-dependent regret upper bound for slowly varying non-stationary bandits.
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.
The paper achieves nearly optimal regret bounds for contextual multinomial logit bandits.
problem The contextual multinomial logit (MNL) bandit problem with varying rewards.
method Established lower bounds and proposed OFU-MNL+ algorithm with matching upper bounds.
result Achieved minimax optimal regret bounds for both uniform and non-uniform reward settings.
EQO uses a simple bonus term for efficient exploration in tabular RL.
problem Achieving minimax optimal reinforcement learning with practical efficiency.
method Exploration via Quasi-Optimism, employing a bonus proportional to state-action visit count.
result Achieves the sharpest known regret bound for tabular RL.
Bandit Phase Retrievalstat.ML
Improved regret bounds for bandit phase retrieval.
problem Minimizing cumulative and simple regret in a bandit phase retrieval problem.
method Proved minimax cumulative and simple regret bounds using adaptive algorithms.
result Minimax cumulative regret is and minimax simple regret is .