Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff

2024-05-28 · Jian Qian, Haichen Hu, David Simchi-Levi

Motivated by the recent discovery of a statistical and computational reduction from contextual bandits to offline regression (Simchi-Levi and Xu, 2021), we address the general (stochastic) Contextual Markov Decision Process (CMDP) problem with horizon H (as known as CMDP with H layers). In this paper, we introduce a reduction from CMDPs to offline density estimation under the realizability assumption, i.e., a model class M containing the true underlying CMDP is provided in advance. We develop an efficient, statistically near-optimal algorithm requiring only O(HlogT) calls to an offline density estimation algorithm (or oracle) across all T rounds of interaction. This number can be further reduced to O(HloglogT) if T is known in advance. Our results mark the first efficient and near-optimal reduction from CMDPs to offline density estimation without imposing any structural assumptions on the model class. A notable feature of our algorithm is the design of a layerwise exploration-exploitation tradeoff tailored to address the layerwise structure of CMDPs. Additionally, our algorithm is versatile and applicable to pure exploration tasks in reward-free reinforcement learning.

📄 PDF Abstract BibTeX arXiv:2405.17796

Code (0)

등록된 구현이 없습니다.

Tasks

Density Estimation Multi-Armed Bandits

Eluder-based Regret for Stochastic Contextual MDPs

2022-11-27 · Orin Levy, Asaf Cassel, Alon Cohen, Yishay Mansour

We present the E-UC$^3$RL algorithm for regret minimization in Stochastic Contextual Markov Decision Processes (CMDPs). The algorithm operates under the minimal assumptions of realizable function class and access to \emp…

regression

Adaptive Estimation and Optimal Control in Offline Contextual MDPs without Stationarity

2026-05-05 · Riddhiman Bhattacharyya, Sayak Chakrabarty, Imon Banerjee arxiv

Contextual MDPs are powerful tools with wide applicability in areas from biostatistics to machine learning. However, specializing them to offline datasets has been challenging due to a lack of robust, theoretically backe…

Representation Learning for Online and Offline RL in Low-rank MDPs

2021-10-09 · ICLR 2022 4 · Masatoshi Uehara, Xuezhou Zhang, Wen Sun

This work studies the question of Representation Learning in RL: how can we learn a compact low-dimensional representation such that on top of the representation we can perform RL procedures such as exploration and explo…

Offline RL Representation Learning

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits

2026-02-10 · Hao Qin, Chicheng Zhang arxiv

We propose an algorithmic framework, Offline Estimation to Decisions (OE2D), that efficiently reduces contextual bandit learning with general reward function approximation to offline regression. The framework allows near…

Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

2026-05-01 · Haichen Hu, Jian Qian, David Simchi-Levi arxiv

Reinforcement learning (RL) in large environments often suffers from severe computational bottlenecks, as conventional regret minimization algorithms require repeated, costly calls to planning and statistical estimation …

Reinforcement Learning