Proposes Optimistic Pessimistically Initialised Q-Learning (OPIQ) for better exploration in RL.
problem Pessimistic initialisation of Q-values in deep RL leads to poor exploration performance.
method Augments pessimistically initialised Q-values with count-based bonuses to ensure optimism.
result OPIQ outperforms non-optimistic DQN variants in hard exploration tasks.
Proposes H-UCRL for efficient model-based RL with sublinear regret.
problem Greedy policy exploration in model-based RL ignores epistemic uncertainty.
method Reparameterizes plausible models, hallucinates control, augments input space, solves with greedy planners.
result H-UCRL achieves provably sublinear regret for Gaussian Process models.
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…
Efficiently solves exploration-exploitation in LQR using Lagrangian relaxation.
problem Exploration-exploitation dilemma in linear quadratic regulator (LQR) setting.
method Relax optimistic optimization into a constrained extended LQR problem, then solve using Riccati equations.
result Computes ε ε ε -optimistic controller efficiently with O ( log ( 1 / ε ) ) O\big(\log(1/ε)\big) O ( log ( 1/ ε ) ) Riccati equations. New algorithm reduces regret in sequential decision-making problems.
problem Balancing exploration and exploitation in online sequential decision problems.
method Variational Bayesian optimistic sampling (VBOS) for optimizing policies.
result VBOS achieves i l d e O ( A T ) ilde O(\sqrt{AT}) i l d e O ( A T ) Bayesian regret for stochastic multi-armed bandits. Optimistic NPG improves policy optimization in online RL with efficient sample complexity.
problem Limited theoretical understanding of policy optimization, especially in online RL.
method Combines natural policy gradient with optimistic policy evaluation.
result Achieves optimal dimension dependence sample complexity for learning near-optimal policies.
Omega method mitigates noise in stochastic game optimization.
problem Noise sensitivity and convergence issues in stochastic game optimization.
method Omega method incorporates EMA of historic gradients in its update rule.
result Omega method outperforms optimistic gradient method in stochastic games.
The paper analyzes CMDPs, balancing exploration and exploitation to avoid constraint violations.
problem Balancing exploration and exploitation in CMDPs to satisfy constraints.
method Two approaches: optimistic planning and incremental updates of primal and dual variables.
result Both approaches achieve sublinear regret on utility and constraint violations, with stronger guarantees for the linear programming approach.
Optimistic Actor-Critic improves exploration efficiency in reinforcement learning.
problem Poor sample efficiency in existing actor-critic methods.
method Introduces Optimistic Actor-Critic, approximating upper and lower bounds on state-action value function.
result Achieves state-of-the-art sample efficiency in challenging continuous control tasks.
OPPO optimizes policy learning with provable efficiency.
problem Designing efficient policy optimization algorithms that incorporate exploration.
method Proposes an Optimistic Proximal Policy Optimization (OPPO) algorithm.
result Achieves i l d e O ( d 2 H 3 T ) ilde{O}(\sqrt{d^2 H^3 T} ) i l d e O ( d 2 H 3 T ) regret in episodic MDPs. Free lunch from noise reveals linear spectral features for RL.
problem Trade-off between expressiveness and tractability in RL.
method Noise assumption and Spectral Dynamics Embedding (SPEDE).
result SPEDE breaks the trade-off and completes optimistic exploration.
New algorithm explores reinforcement learning with noisy data.
problem Exploration in reinforcement learning with complex value functions.
method Randomized exploration with i.i.d. scalar noises and optimistic reward sampling.
result Achieves worst-case regret bound of O ~ ( p o l y ( d E H ) T ) \widetilde{O}(\mathrm{poly}(d_EH)\sqrt{T}) O ( poly ( d E H ) T ) . Optimistic algorithms and Thompson sampling use info-theory for better reinforcement learning.
problem Designing algorithms that balance exploration and exploitation in reinforcement learning.
method Integrating information-theoretic concepts into optimistic algorithms and Thompson sampling.
result Cumulative regret bound depends on uncertainty and quantifies prior information value.
New approach uses unlabeled prior data to accelerate exploration in sparse reward tasks.
problem Sparse reward tasks in reinforcement learning.
method Learn reward model from online experience, label prior data, and use concurrently.
result Rapid exploration in challenging sparse-reward domains.
Optimistic RL algorithms are simplified for deep RL with competitive performance.
problem Achieving accurate optimism in model-based RL for large-scale problems.
method Interpreting scalable optimistic model-based algorithms as solving a tractable noise augmented MDP.
result Competitive regret bound of i l d e O ( ∣ S ∣ H ∣ A ∣ T ) ilde{\mathcal{O}}( |\mathcal{S}|H\sqrt{|\mathcal{A}| T } ) i l d e O ( ∣ S ∣ H ∣ A ∣ T ) for Gaussian noise augmentation. Model-based Bayesian Reinforcement Learning (BRL) allows a found formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work r…
Optimistic actor-critic tackles linear MDPs with parametric policies.
problem Theoretical limitations of existing actor-critic methods for linear MDPs.
method Proposes an optimistic actor-critic framework with parametric log-linear policies and approximate Thompson sampling.
result Achieves state-of-the-art sample complexity in both on-policy and off-policy settings.
New method boosts skill learning by encouraging optimistic exploration.
problem Intrinsic reward for exploration is inherently pessimistic.
method Derive an information gain auxiliary objective involving an ensemble of discriminators and rewarding policy disagreement.
result Improves skill learning in grid worlds and Atari games.
New rule reduces exploration regret to logarithmic, improving bad episode handling.
problem Improving exploration regret in average reward MDPs.
method Replacing Doubling Trick with Vanishing Multiplicative rule in EVI-based algorithms.
result Regret is logarithmic under the new rule, significantly better than linear.
This paper analyzes how randomizing rewards in MBRL can improve performance without being overly optimistic.
problem The gap between theoretical worst-case regret analysis and empirical performance in MBRL.
method Reward randomization in model-based reinforcement learning (MBRL) with kernelized linear regulator (KNR) model.
result Reward randomization guarantees partial optimism and near-optimal worst-case regret.
RandQL is a new model-free algorithm for MDPs with a novel learning rate randomization approach.
problem Minimizing regret in episodic MDPs with model-free methods.
method Randomized Q-learning with learning rate randomization.
result RandQL achieves optimal regret bounds in both tabular and metric state-action spaces.
Robust Optimization has traditionally taken a pessimistic, or worst-case viewpoint of uncertainty which is motivated by a desire to find sets of optimal policies that maintain feasibility under a variety of operating conditions. In this paper, we explore an optimistic, or best-case view of uncertainty and show that it …
New RL algorithm optimizes policies with bandit feedback, matching previous bounds.
problem Optimizing policies with unknown transitions and bandit feedback.
method Optimistic Trust Region Policy Optimization (TRPO) algorithm.
result Sub-linear regret bounds for both stochastic and adversarial rewards.
New batch RL method avoids overly optimistic policies.
problem Challenges in applying RL to large domains with limited data.
method Modified Bellman optimality and evaluation back-up for conservative updates.
result Can find approximately best policies within explored state-action space.
New RL algorithm tackles online robust MDPs with uncertainty.
problem Developing robust reinforcement learning models for real-world environments.
method Proposes a robust optimistic policy optimization algorithm for online robust MDPs.
result Establishes the first regret bound for online robust MDPs.
New framework improves learning across multiple distributions.
problem Modeling uncertainty in sensitive machine learning applications.
method Inspired by multi-armed bandits, provides distribution-dependent guarantees.
result Enhanced dependence on suboptimality gaps and sample size.
Bayesian classifier improves robustness with optimistic score ratio.
problem Limited information on class-conditional distribution.
method Optimistic score ratio for robust binary classification.
result Bayesian classifier using optimistic score ratio is robust and computationally tractable.
Study designs steering rewards for MFGs with unknown dynamics and model uncertainty.
problem Designing incentives for large populations of agents in MFGs with uncertain model details.
method Developed optimistic exploration algorithms for agents with no-adaptive regret behaviors.
result Sub-linear regret guarantees for cumulative gaps between agent behaviors and desired outcomes.
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 4π^2 4 π 2 .
The thesis optimizes quantum state exploration using bandit algorithms.
problem Maximizing reward in online learning of quantum state properties.
method Multi-armed bandit approach to select observables, minimizing regret.
result Optimal strategies with matching upper and lower bounds for regret.
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.
problem Evaluating the potential of nonlinear models in fitting.
method Proposes an optimistic estimate to quantify the smallest sample size for fitting nonlinear models.
result Predicts specific subsets of targets that can be fitted at overparameterization.
This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most prior settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables …
Characterizes concept classes for optimistic online learning.
problem Understanding minimal assumptions for online learnability.
method Investigates two questions about concept classes' learnability.
result Characterizes all concept classes for optimistically universal online learnability.
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 O ( l o g N N ) \mathcal{O}(\frac{logN}{\sqrt{N}}) O ( N l o g N ) to O ( e − N ) \mathcal O(e^{-\sqrt{N}}) O ( e − N ) , where N N N is the number of evaluations. This paper exp…
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…
While designing the state space of an MDP, it is common to include states that are transient or not reachable by any policy (e.g., in mountain car, the product space of speed and position contains configurations that are not physically reachable). This leads to defining weakly-communicating or multi-chain MDPs. In this…
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.
New algorithms reduce forecasting errors by leveraging optimistic learning and hinting.
problem Real-time climate forecasting with delayed feedback.
method Developed optimistic online learning algorithms that reduce regret under delayed feedback.
result Optimistic learning algorithms achieve optimal regret guarantees under delayed feedback.
In many cases an intelligent agent may want to learn how to mimic a single observed demonstrated trajectory. In this work we consider how to perform such procedural learning from observation, which could help to enable agents to better use the enormous set of video data on observation sequences. Our approach exploits t…
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.
Unified framework for model- and value-optimistic reinforcement learning.
problem Designing and analyzing algorithms for episodic reinforcement learning.
method Lagrangian duality for a unified view of optimism.
result Unified algorithms with both efficient implementation and probabilistic analysis.
New algorithms ensure policies perform at least as good as a baseline in reinforcement learning.
problem Learning policies that are guaranteed to perform at least as well as a baseline in reinforcement learning.
method Introduce conservative exploration for average reward and finite horizon problems, presenting two optimistic algorithms.
result Guaranteed performance of policies at least as good as a baseline, without hindering learning ability.
New algorithm fills gaps in offline data for hybrid RL, achieving similar gains without coverage assumptions.
problem Lack of provable benefits in hybrid RL with coverage assumptions.
method Warm-starting optimistic online algorithms with offline data in experience replay buffer.
result Hybrid RL gains similar to offline-only RL without coverage assumptions, demonstrating efficient exploration.
Kernel-UCBVI algorithm balances exploration and exploitation in metric state-action spaces.
problem Exploration-exploitation dilemma in finite-horizon reinforcement learning with metric state-action spaces.
method Kernel-UCBVI, leveraging smoothness and kernel estimators of rewards and transitions.
result First regret bound for kernel-based RL using smoothing kernels, O ( H 3 K 2 d / ( 2 d + 1 ) ) O(H^3 K^{2d/(2d+1)}) O ( H 3 K 2 d / ( 2 d + 1 ) ) . Improved RL algorithm reduces regret in large state spaces.
problem Exploration in large or continuous state spaces.
method Optimistically-initialized randomized least-squares value iteration (RLSVI) with function approximation.
result Frequentist regret bound of O ~ ( d 2 H 2 T ) \widetilde O(d^2 H^2 \sqrt{T}) O ( d 2 H 2 T ) for low-rank transition dynamics. 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.
Online Apprenticeship Learning aims to match expert performance without access to cost functions.
problem Learning an agent's policy to match expert performance in an MDP without cost function access.
method Combines mirror descent based no-regret algorithms for policy optimization and cost learning, with optimistic exploration.
result Derives an algorithm with O ( K ) O(\sqrt{K}) O ( K ) regret, practical for high-dimensional control problems.