Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning

2023-04-14 · Gen Li, Yuling Yan, Yuxin Chen, Jianqing Fan

This paper studies reward-agnostic exploration in reinforcement learning (RL) -- a scenario where the learner is unware of the reward functions during the exploration stage -- and designs an algorithm that improves over the state of the art. More precisely, consider a finite-horizon inhomogeneous Markov decision process with $S$ states, $A$ actions, and horizon length $H$, and suppose that there are no more than a polynomial number of given reward functions of interest. By collecting an order of \begin{align*} \frac{SAH^3}{\varepsilon^2} \text{ sample episodes (up to log factor)} \end{align*} without guidance of the reward information, our algorithm is able to find $\varepsilon$-optimal policies for all these reward functions, provided that $\varepsilon$ is sufficiently small. This forms the first reward-agnostic exploration scheme in this context that achieves provable minimax optimality. Furthermore, once the sample size exceeds $\frac{S^2AH^3}{\varepsilon^2}$ episodes (up to log factor), our algorithm is able to yield $\varepsilon$ accuracy for arbitrarily many reward functions (even when they are adversarially designed), a task commonly dubbed as ``reward-free exploration.'' The novelty of our algorithm design draws on insights from offline RL: the exploration scheme attempts to maximize a critical reward-agnostic quantity that dictates the performance of offline RL, while the policy learning paradigm leverages ideas from sample-optimal offline RL paradigms.

📄 PDF Abstract BibTeX arXiv:2304.07278

Code (0)

등록된 구현이 없습니다.

Tasks

Offline RL reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

2026-02-18 · Oran Ridel, Alon Cohen arxiv

We study reward-free and reward-agnostic exploration in episodic finite-horizon Markov decision processes (MDPs), where an agent explores an unknown environment without observing external rewards. Reward-free exploration…

One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning

2022-05-31 · Pedro Cisneros-Velarde, Boxiang Lyu, Sanmi Koyejo, Mladen Kolar

Although parallelism has been extensively used in reinforcement learning (RL), the quantitative effects of parallel exploration are not well understood theoretically. We study the benefits of simple parallel exploration …

Reinforcement Learning (RL)

Nearly Minimax Optimal Reward-free Reinforcement Learning

2020-10-12 · Zihan Zhang, Simon S. Du, Xiangyang Ji

We study the reward-free reinforcement learning framework, which is particularly suitable for batch reinforcement learning and scenarios where one needs policies for multiple reward functions. This framework has two phas…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Task-agnostic Exploration in Reinforcement Learning

2020-06-16 · NeurIPS 2020 12 · Xuezhou Zhang, Yuzhe ma, Adish Singla

Efficient exploration is one of the main challenges in reinforcement learning (RL). Most existing sample-efficient algorithms assume the existence of a single reward function during exploration. In many practical scenari…

Efficient Exploration reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits

2024-10-21 · Brian Cho, Dominik Meier, Kyra Gan, Nathan Kallus

In multi-armed bandits, the tasks of reward maximization and pure exploration are often at odds with each other. The former focuses on exploiting arms with the highest means, while the latter may require constant explora…

Multi-Armed Bandits valid