RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation

• URL: http://arxiv.org/abs/2406.01389v2
• Date: Wed, 26 Jun 2024 15:42:57 GMT
• Title: RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation
• Authors: Jeongyeol Kwon, Shie Mannor, Constantine Caramanis, Yonathan Efroni,
• Abstract summary: We introduce the first sample-efficient algorithm for LMDPs without any additional structural assumptions. We show how these can be used to derive near-optimal guarantees of an optimistic exploration algorithm. These results can be valuable for a wide range of interactive learning problems beyond LMDPs, and especially, for partially observed environments.
• Score: 73.2390735383842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many real-world decision problems there is partially observed, hidden or latent information that remains fixed throughout an interaction. Such decision problems can be modeled as Latent Markov Decision Processes (LMDPs), where a latent variable is selected at the beginning of an interaction and is not disclosed to the agent. In the last decade, there has been significant progress in solving LMDPs under different structural assumptions. However, for general LMDPs, there is no known learning algorithm that provably matches the existing lower bound (Kwon et al., 2021). We introduce the first sample-efficient algorithm for LMDPs without any additional structural assumptions. Our result builds off a new perspective on the role of off-policy evaluation guarantees and coverage coefficients in LMDPs, a perspective, that has been overlooked in the context of exploration in partially observed environments. Specifically, we establish a novel off-policy evaluation lemma and introduce a new coverage coefficient for LMDPs. Then, we show how these can be used to derive near-optimal guarantees of an optimistic exploration algorithm. These results, we believe, can be valuable for a wide range of interactive learning problems beyond LMDPs, and especially, for partially observed environments.

Related papers

• Prospective Side Information for Latent MDPs [80.00842638151558]
  We study the class of LMDPs with em prospective side information, when an agent receives additional, weakly revealing, information at the beginning of each episode. We show that, surprisingly, this problem is not captured by contemporary settings and algorithms designed for partially observed environments. We then establish that any sample efficient algorithm must suffer at least $Omega(K2/3)$-regret, as opposed to standard $Omega(sqrtK)$ lower bounds, and design an algorithm with a matching upper bound.
  arXiv  Detail & Related papers  (2023-10-11T15:37:31Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• Offline Reinforcement Learning with Instrumental Variables in Confounded Markov Decision Processes [93.61202366677526]
  We study the offline reinforcement learning (RL) in the face of unmeasured confounders. We propose various policy learning methods with the finite-sample suboptimality guarantee of finding the optimal in-class policy.
  arXiv  Detail & Related papers  (2022-09-18T22:03:55Z)
• Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
  In episodic Block MDPs, the decision maker has access to rich observations or contexts generated from a small number of latent states. We are first interested in estimating the latent state decoding function based on data generated under a fixed behavior policy. We then study the problem of learning near-optimal policies in the reward-free framework.
  arXiv  Detail & Related papers  (2022-08-17T18:49:53Z)
• A Minimax Learning Approach to Off-Policy Evaluation in Partially Observable Markov Decision Processes [31.215206208622728]
  We consider off-policy evaluation (OPE) in Partially Observable Markov Decision Processes (POMDPs) Existing methods suffer from either a large bias in the presence of unmeasured confounders, or a large variance in settings with continuous or large observation/state spaces. We first propose novel identification methods for OPE in POMDPs with latent confounders, by introducing bridge functions that link the target policy's value and the observed data distribution.
  arXiv  Detail & Related papers  (2021-11-12T15:52:24Z)
• Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes [65.91730154730905]
  In applications of offline reinforcement learning to observational data, such as in healthcare or education, a general concern is that observed actions might be affected by unobserved factors. Here we tackle this by considering off-policy evaluation in a partially observed Markov decision process (POMDP) We extend the framework of proximal causal inference to our POMDP setting, providing a variety of settings where identification is made possible.
  arXiv  Detail & Related papers  (2021-10-28T17:46:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.