arXiv research

New method for optimistic planning in MDPs using regularization.

New algorithm reduces reinforcement learning regret to sqrt(T) without strong dynamics assumptions.

Algorithm converges to Nash equilibria in competitive games.

Efficiently solves exploration-exploitation in LQR using Lagrangian relaxation.

In this paper, we prove some convergence results of a special case of optimistic policy iteration algorithm for stochastic shortest path problem. We consider both Monte Carlo and $TD(λ)$ methods for the policy evaluation step under the condition that the termination state will eventually be reached almost surely.

Improved convergence rates for saddle-point optimization algorithms.

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

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…

Adaptive discretization improves model-based RL in large spaces.

New algorithm explores reinforcement learning with noisy data.

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

We study the iteration complexity of the optimistic gradient descent-ascent (OGDA) method and the extra-gradient (EG) method for finding a saddle point of a convex-concave unconstrained min-max problem. To do so, we first show that both OGDA and EG can be interpreted as approximate variants of the proximal point method…

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…

We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL). When the state space is large or continuous, traditional tabular approaches are unfeasible and some form of function approximation is mandatory. In this paper, we introduce an optimistically-initialized variant of the popula…

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

New algorithm identifies near-optimal policies in adversarial distributed RL settings.

Accelerates policy optimization in RL with optimistic and adaptive updates.

Develops new algorithms for solving root-finding problems in large-scale settings.

We consider model-based reinforcement learning in finite Markov De- cision Processes (MDPs), focussing on so-called optimistic strategies. In MDPs, optimism can be implemented by carrying out extended value it- erations under a constraint of consistency with the estimated model tran- sition probabilities. The UCRL2 alg…

Unified framework for model- and value-optimistic reinforcement learning.

PROPO tackles non-stationary MDPs with efficient policy optimization.

In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of \t…

Optimistic algorithm reduces regret in non-stationary linear MDPs.

Model-free reinforcement learning algorithms combined with value function approximation have recently achieved impressive performance in a variety of application domains. However, the theoretical understanding of such algorithms is limited, and existing results are largely focused on episodic or discounted Markov decis…

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

New algorithm reduces sample size for robust reinforcement learning.

The CFR framework has been a powerful tool for solving large-scale extensive-form games in practice. However, the theoretical rate at which past CFR-based algorithms converge to the Nash equilibrium is on the order of $O(T^{-1/2})$, where $T$ is the number of iterations. In contrast, first-order methods can be used to …

New ODE models show saddle-point optimization methods converge differently, with last-iterate convergence for OGDA.

We consider the problem of minimizing a smooth convex function by reducing the optimization to computing the Nash equilibrium of a particular zero-sum convex-concave game. Zero-sum games can be solved using online learning dynamics, where a classical technique involves simulating two no-regret algorithms that play agai…

Kernel-based function approximation improves reinforcement learning performance.

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 …

Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al \cite{DISZ17} and follow-up work of Liang and Stokes \cite{LiangS18} have established that a variant of the widely used Gradient Descent/Ascent procedure, called "Optimistic Gradient Descent/Asce…

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

StoSOO optimistically maximizes noisy, locally smooth functions.

New RL algorithm tackles large state spaces using optimistic function approximation.

New rule reduces exploration regret to logarithmic, improving bad episode handling.

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

Real-world applications require RL algorithms to act safely. During learning process, it is likely that the agent executes sub-optimal actions that may lead to unsafe/poor states of the system. Exploration is particularly brittle in high-dimensional state/action space due to increased number of low-performing actions. …

Optimistic PPO variant solves linear MDPs with improved regret bound.

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

Solves open problem on universally consistent online learning with unbounded losses.

We analyze reinforcement learning algorithms using a distributional approach.

We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs. We show that an optimistic modification to value iteration achieves a regret bound of $\tilde{O}( \sqrt{HSAT} + H^2S^2A+H\sqrt{T})$ where $H$ is the time horizon, $S$ the number of states, $A$ the number of action…

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

We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online…

Optimistic actor-critic tackles linear MDPs with parametric policies.

New RL method handles large state-action spaces with complex models.

Bayesian classifier improves robustness with optimistic score ratio.