arXiv research

New framework for Adam-type algorithms with constant β1, improving regret analysis.

Improved analysis of UCRL2 with empirical Bernstein inequality reduces exploration-exploitation regret.

Improved dynamic regret analysis for strongly convex and smooth functions.

Optimistic Hedge achieves optimal regret bounds in two-player zero-sum games.

SCaLE tackles dynamic regret in noisy bandit feedback with switching costs.

Significant improvements in regret analysis for adaptive online learning problems.

This paper analyzes data-driven Newsvendor problems and finds a wide range of possible regrets.

New analysis shows how temporal variability affects online learning performance.

Study on regret minimization in deterministic MDPs.

Study shows certainty equivalent policy minimizes regret in continuous-time systems.

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…

Unified analysis of Gaussian Process Thompson Sampling without discretization.

The paper tackles robust policy learning from multiple data sources.

We propose algorithms for online principal component analysis (PCA) and variance minimization for adaptive settings. Previous literature has focused on upper bounding the static adversarial regret, whose comparator is the optimal fixed action in hindsight. However, static regret is not an appropriate metric when the un…

This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given…

Mirror descent with an entropic regularizer is known to achieve shifting regret bounds that are logarithmic in the dimension. This is done using either a carefully designed projection or by a weight sharing technique. Via a novel unified analysis, we show that these two approaches deliver essentially equivalent bounds …

Ensemble sampling approximates Thompson sampling for complex models.

Improved regret bounds for structured linear contextual bandits with Gaussian noise.

Improved Thompson Sampling reduces regret in contextual bandits and reinforcement learning.

We consider an online learning process to forecast a sequence of outcomes for nonconvex models. A typical measure to evaluate online learning algorithms is regret but such standard definition of regret is intractable for nonconvex models even in offline settings. Hence, gradient based definition of regrets are common f…

New insights into balancing reward and fairness in stochastic MAB.

Improved FPL algorithms for adversarial MDPs with better regret bounds.

New model-free algorithm achieves similar LQR regret guarantees.

Paper improves regret bounds for Gaussian process upper confidence bound in Bayesian optimization.

Randomized exploration in linear bandits achieves optimal regret bounds.

Improved regret bound for linear ensemble sampling.

New algorithm reduces reinforcement learning regret by adapting to interaction variability.

The paper tackles personalized policy learning from diverse data sources in a federated setting.

Improved analysis of UCBVI algorithm with better empirical performance.

New framework analyzes regret in guided diffusion for optimizing structured inputs.

New method minimizes regret in AMDP with high probability.

We discuss a multiple-play multi-armed bandit (MAB) problem in which several arms are selected at each round. Recently, Thompson sampling (TS), a randomized algorithm with a Bayesian spirit, has attracted much attention for its empirically excellent performance, and it is revealed to have an optimal regret bound in the…

New method for semiparametric bandits reduces regret to optimal levels.

Improved Thompson Sampling using fractional posteriors achieves better regret bounds.

Paper develops robust estimators and strategies for stochastic MABs with heavy-tailed rewards.

Study on policy gradient for stochastic bandits using diffusion approximation.

Paper introduces a new $G^\star$ regret measure for online convex optimization with smooth losses.

Improved risk-sensitive RL with exponential Bellman equation and better regret bounds.

GN algorithm solves batched bandit for nondegenerate functions near-optimally.

Extended analysis of Q-learning's efficiency, matching optimal regret.

New approach limits regret in non-stationary bandits.

The study compares uniform-price and discriminatory auctions in terms of learning difficulty.

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…

Fine-grained gap-dependent regret bounds for reinforcement learning.

The paper extends Thompson Sampling to infinite action spaces using information theory.

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\wid…

The paper addresses frequentist regret of Linear Thompson Sampling in stochastic linear bandits.

Paper analyzes faster convergence rates for reinforcement learning from offline data.