Exploration in Structured Reinforcement Learning

2018-06-03 · NeurIPS 2018 12 · Jungseul Ok, Alexandre Proutiere, Damianos Tranos

We address reinforcement learning problems with finite state and action spaces where the underlying MDP has some known structure that could be potentially exploited to minimize the exploration rates of suboptimal (state, action) pairs. For any arbitrary structure, we derive problem-specific regret lower bounds satisfied by any learning algorithm. These lower bounds are made explicit for unstructured MDPs and for those whose transition probabilities and average reward functions are Lipschitz continuous w.r.t. the state and action. For Lipschitz MDPs, the bounds are shown not to scale with the sizes $S$ and $A$ of the state and action spaces, i.e., they are smaller than $c\log T$ where $T$ is the time horizon and the constant $c$ only depends on the Lipschitz structure, the span of the bias function, and the minimal action sub-optimality gap. This contrasts with unstructured MDPs where the regret lower bound typically scales as $SA\log T$. We devise DEL (Directed Exploration Learning), an algorithm that matches our regret lower bounds. We further simplify the algorithm for Lipschitz MDPs, and show that the simplified version is still able to efficiently exploit the structure.

📄 PDF Abstract BibTeX arXiv:1806.00775

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Meta-Reinforcement Learning of Structured Exploration Strategies

2018-02-20 · NeurIPS 2018 12 · Abhishek Gupta, Russell Mendonca, Yuxuan Liu, Pieter Abbeel 외

Exploration is a fundamental challenge in reinforcement learning (RL). Many of the current exploration methods for deep RL use task-agnostic objectives, such as information gain or bonuses based on state visitation. Howe…

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

STRIVE: Structured Spatiotemporal Exploration for Reinforcement Learning in Video Question Answering

2026-04-02 · Emad Bahrami, Olga Zatsarynna, Parth Pathak, Sunando Sengupta 외 arxiv

We introduce STRIVE (SpatioTemporal Reinforcement with Importance-aware Variant Exploration), a structured reinforcement learning framework for video question answering. While group-based policy optimization methods have…

Video Question Answering Reinforcement Learning

Goal-Guided Efficient Exploration via Large Language Model in Reinforcement Learning

2025-09-26 · Yajie Qi, Wei Wei, Lin Li, Lijun Zhang 외 arxiv

Real-world decision-making tasks typically occur in complex and open environments, posing significant challenges to reinforcement learning (RL) agents' exploration efficiency and long-horizon planning capabilities. A pro…

Reinforcement Learning

Perturbation-based exploration methods in deep reinforcement learning

2020-11-10 · Sneha Aenugu

Recent research on structured exploration placed emphasis on identifying novel states in the state space and incentivizing the agent to revisit them through intrinsic reward bonuses. In this study, we question whether th…

Atari Games Benchmarking Deep Reinforcement Learning reinforcement-learning+2

Random Latent Exploration for Deep Reinforcement Learning

2024-07-18 · Srinath Mahankali, Zhang-Wei Hong, Ayush Sekhari, Alexander Rakhlin 외

The ability to efficiently explore high-dimensional state spaces is essential for the practical success of deep Reinforcement Learning (RL). This paper introduces a new exploration technique called Random Latent Explorat…

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