arXiv research

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

Optimistic bounds for multi-output learning using self-bounding Lipschitz condition.

New method minimizes regret in AMDP with high probability.

Novel approach to universal online learning for bounded losses, closing open problems.

Optimistic PPO variant solves linear MDPs with improved regret bound.

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…

Improved regret bounds for online convex optimization under stochastic and adversarial settings.

Safe linear bandits over unknown polytopes avoid safety violations and suboptimal actions.

Optimistic RL algorithms are simplified for deep RL with competitive performance.

A generalized optimistic method for saddle point problems with improved complexity.

StoSOO optimistically maximizes noisy, locally smooth functions.

Optimistic method adapted for faster convex-concave min-max problems.

Optimistic algorithm reduces regret and constraint violations in online convex optimization with adversarial constraints.

Study optimizes linear regression analysis for high-dimensional settings.

Proposes H-UCRL for efficient model-based RL with sublinear regret.

New algorithm achieves data-dependent regret bounds in MDPs with unknown transitions.

We consider the problem of online planning in a Markov Decision Process when given only access to a generative model, restricted to open-loop policies - i.e. sequences of actions - and under budget constraint. In this setting, the Open-Loop Optimistic Planning (OLOP) algorithm enjoys good theoretical guarantees but is …

New RL algorithm optimizes policies with bandit feedback, matching previous bounds.

New algorithms reduce regret in online MDPs by adapting to data and variance.

Accelerates policy optimization in RL with optimistic and adaptive updates.

We address the issue of limit cycling behavior in training Generative Adversarial Networks and propose the use of Optimistic Mirror Decent (OMD) for training Wasserstein GANs. Recent theoretical results have shown that optimistic mirror decent (OMD) can enjoy faster regret rates in the context of zero-sum games. WGANs …

New RL algorithm tackles online robust MDPs with uncertainty.

New algorithm reduces regret in delayed feedback generalised linear bandits.

Bayesian classifier improves robustness with optimistic score ratio.

We propose a new variant of AMSGrad, a popular adaptive gradient based optimization algorithm widely used for training deep neural networks. Our algorithm adds prior knowledge about the sequence of consecutive mini-batch gradients and leverages its underlying structure making the gradients sequentially predictable. By …

We show that the optimistic limits of the colored Jones polynomials of the hyperbolic knots coincide with the optimistic limits of the Kashaev invariants modulo $4π^2$.

PROPO tackles non-stationary MDPs with efficient policy optimization.

Proposes Optimistic Pessimistically Initialised Q-Learning (OPIQ) for better exploration in RL.

We design a new provably efficient algorithm for episodic reinforcement learning with generalized linear function approximation. We analyze the algorithm under a new expressivity assumption that we call "optimistic closure," which is strictly weaker than assumptions from prior analyses for the linear setting. With opti…

Unified CS for GLMs improves bandit regret bounds.

We discuss the relative merits of optimistic and randomized approaches to exploration in reinforcement learning. Optimistic approaches presented in the literature apply an optimistic boost to the value estimate at each state-action pair and select actions that are greedy with respect to the resulting optimistic value f…

The optimistic limit is the mathematical formulation of the classical limit which is a physical method to expect the actual limit by using saddle point method of certain potential function. The original optimistic limit of the Kashaev invariant was formulated by Yokota, and a modified formulation was suggested by the a…

Optimistic estimate predicts best fitting performance of nonlinear models.

New principle optimizes bandit decisions with context.

Bayesian optimisation (BO) is a well-known efficient algorithm for finding the global optimum of expensive, black-box functions. The current practical BO algorithms have regret bounds ranging from $\mathcal{O}(\frac{logN}{\sqrt{N}})$ to $\mathcal O(e^{-\sqrt{N}})$, where $N$ is the number of evaluations. This paper exp…

New algorithm reduces regret in sequential decision-making problems.

Unified algorithm for optimizing rewards in stochastic path problems.

New RL algorithm tackles nonstationary MDPs with linear approximations and varying rewards.

This paper analyzes OGDA and EG methods for nonconvex minimax problems.

A new policy for contextual bandits adapts to reward vector shifts.

Optimistic NPG improves policy optimization in online RL with efficient sample complexity.

Characterizes concept classes for optimistic online learning.

Improved model-free reinforcement learning with decision-estimation coefficient.

We show how to take any two parameter-free online learning algorithms with different regret guarantees and obtain a single algorithm whose regret is the minimum of the two base algorithms. Our method is embarrassingly simple: just add the iterates. This trick can generate efficient algorithms that adapt to many norms s…

An algorithm for maximizing rewards under linear cost constraints.

We give a simple optimistic algorithm for which it is easy to derive regret bounds of $\tilde{O}(\sqrt{t_{\rm mix} SAT})$ after $T$ steps in uniformly ergodic Markov decision processes with $S$ states, $A$ actions, and mixing time parameter $t_{\rm mix}$. These bounds are the first regret bounds in the general, non-epi…

New algorithms reduce forecasting errors by leveraging optimistic learning and hinting.

Optimistic Thompson Sampling reduces regret in unknown multi-player games.