Provably Efficient Offline Reinforcement Learning in Regular Decision Processes

2023-09-21 · NeurIPS 2023 11

This paper deals with offline (or batch) Reinforcement Learning (RL) in episodic Regular Decision Processes (RDPs). RDPs are the subclass of Non-Markov Decision Processes where the dependency on the history of past events can be captured by a finite-state automaton. We consider a setting where the automaton that underlies the RDP is unknown, and a learner strives to learn a near-optimal policy using pre-collected data, in the form of non-Markov sequences of observations, without further exploration. We present RegORL, an algorithm that suitably combines automata learning techniques and state-of-the-art algorithms for offline RL in MDPs. RegORL has a modular design allowing one to use any off-the-shelf offline RL algorithm in MDPs. We report a non-asymptotic high-probability sample complexity bound for RegORL to yield an $\varepsilon$-optimal policy, which makes appear a notion of concentrability relevant for RDPs. Furthermore, we present a sample complexity lower bound for offline RL in RDPs. To our best knowledge, this is the first work presenting a provably efficient algorithm for offline learning in RDPs.Submission Number: 14017

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes

2022-05-26 · Miao Lu, Yifei Min, Zhaoran Wang, Zhuoran Yang

We study offline reinforcement learning (RL) in partially observable Markov decision processes. In particular, we aim to learn an optimal policy from a dataset collected by a behavior policy which possibly depends on the…

Causal Inference Offline RL Reinforcement Learning (RL)

Offline-Online Reinforcement Learning for Linear Mixture MDPs

2026-04-13 · Zhongjun Zhang, Sean R. Sinclair arxiv

We study offline-online reinforcement learning in linear mixture Markov decision processes (MDPs) under environment shift. In the offline phase, data are collected by an unknown behavior policy and may come from a mismat…

Reinforcement Learning

Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL

2021-06-22 · Weitong Zhang, Jiafan He, Dongruo Zhou, Amy Zhang 외

The success of deep reinforcement learning (DRL) lies in its ability to learn a representation that is well-suited for the exploration and exploitation task. To understand how the choice of representation can improve the…

Deep Reinforcement Learning Offline RL reinforcement-learning Reinforcement Learning+2

On the connection between Bregman divergence and value in regularized Markov decision processes

2022-10-21 · Brendan O'Donoghue

In this short note we derive a relationship between the Bregman divergence from the current policy to the optimal policy and the suboptimality of the current value function in a regularized Markov decision process. This …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Near-Optimal Offline Reinforcement Learning via Double Variance Reduction

2021-02-02 · NeurIPS 2021 12 · Ming Yin, Yu Bai, Yu-Xiang Wang

We consider the problem of offline reinforcement learning (RL) -- a well-motivated setting of RL that aims at policy optimization using only historical data. Despite its wide applicability, theoretical understandings of …

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