Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory

• URL: http://arxiv.org/abs/2410.03016v1
• Date: Thu, 3 Oct 2024 21:57:21 GMT
• Title: Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory
• Authors: Alexander Levine, Peter Stone, Amy Zhang,
• Abstract summary: STEEL is the first provably sample-efficient algorithm for learning the controllable dynamics of an Exogenous Block Markov Decision Process from a single trajectory. We prove that STEEL is correct and sample-efficient, and demonstrate STEEL on two toy problems.
• Score: 87.62730694973696
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In order to train agents that can quickly adapt to new objectives or reward functions, efficient unsupervised representation learning in sequential decision-making environments can be important. Frameworks such as the Exogenous Block Markov Decision Process (Ex-BMDP) have been proposed to formalize this representation-learning problem (Efroni et al., 2022b). In the Ex-BMDP framework, the agent's high-dimensional observations of the environment have two latent factors: a controllable factor, which evolves deterministically within a small state space according to the agent's actions, and an exogenous factor, which represents time-correlated noise, and can be highly complex. The goal of the representation learning problem is to learn an encoder that maps from observations into the controllable latent space, as well as the dynamics of this space. Efroni et al. (2022b) has shown that this is possible with a sample complexity that depends only on the size of the controllable latent space, and not on the size of the noise factor. However, this prior work has focused on the episodic setting, where the controllable latent state resets to a specific start state after a finite horizon. By contrast, if the agent can only interact with the environment in a single continuous trajectory, prior works have not established sample-complexity bounds. We propose STEEL, the first provably sample-efficient algorithm for learning the controllable dynamics of an Ex-BMDP from a single trajectory, in the function approximation setting. STEEL has a sample complexity that depends only on the sizes of the controllable latent space and the encoder function class, and (at worst linearly) on the mixing time of the exogenous noise factor. We prove that STEEL is correct and sample-efficient, and demonstrate STEEL on two toy problems. Code is available at: https://github.com/midi-lab/steel.

Related papers

• Bidirectional Decoding: Improving Action Chunking via Closed-Loop Resampling [51.38330727868982]
  Bidirectional Decoding (BID) is a test-time inference algorithm that bridges action chunking with closed-loop operations. We show that BID boosts the performance of two state-of-the-art generative policies across seven simulation benchmarks and two real-world tasks.
  arXiv  Detail & Related papers  (2024-08-30T15:39:34Z)
• A Dual Approach to Imitation Learning from Observations with Offline Datasets [19.856363985916644]
  Demonstrations are an effective alternative to task specification for learning agents in settings where designing a reward function is difficult. We derive DILO, an algorithm that can leverage arbitrary suboptimal data to learn imitating policies without requiring expert actions.
  arXiv  Detail & Related papers  (2024-06-13T04:39:42Z)
• Learning Action-based Representations Using Invariance [18.1941237781348]
  We introduce action-bisimulation encoding, which learns a multi-step controllability metric that discounts distant state features that are relevant for control. We demonstrate that action-bisimulation pretraining on reward-free, uniformly random data improves sample efficiency in several environments.
  arXiv  Detail & Related papers  (2024-03-25T02:17:54Z)
• Multistep Inverse Is Not All You Need [87.62730694973696]
  In real-world control settings, the observation space is often unnecessarily high-dimensional and subject to time-correlated noise. It is therefore desirable to learn an encoder to map the observation space to a simpler space of control-relevant variables. We propose a new algorithm, ACDF, which combines multistep-inverse prediction with a latent forward model.
  arXiv  Detail & Related papers  (2024-03-18T16:36:01Z)
• Latent Exploration for Reinforcement Learning [87.42776741119653]
  In Reinforcement Learning, agents learn policies by exploring and interacting with the environment. We propose LATent TIme-Correlated Exploration (Lattice), a method to inject temporally-correlated noise into the latent state of the policy network.
  arXiv  Detail & Related papers  (2023-05-31T17:40:43Z)
• STMixer: A One-Stage Sparse Action Detector [48.0614066856134]
  We propose a new one-stage action detector, termed STMixer. We present a query-based adaptive feature sampling module, which endows our STMixer with the flexibility of mining a set of discriminative video features. We obtain the state-of-the-art results on the datasets of AVA, UCF101-24, and JHMDB.
  arXiv  Detail & Related papers  (2023-03-28T10:47:06Z)
• Provable RL with Exogenous Distractors via Multistep Inverse Dynamics [85.52408288789164]
  Real-world applications of reinforcement learning (RL) require the agent to deal with high-dimensional observations such as those generated from a megapixel camera. Prior work has addressed such problems with representation learning, through which the agent can provably extract endogenous, latent state information from raw observations. However, such approaches can fail in the presence of temporally correlated noise in the observations.
  arXiv  Detail & Related papers  (2021-10-17T15:21:27Z)
• Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting [60.98700344526674]
  Low-complexity models such as linear function representation play a pivotal role in enabling sample-efficient reinforcement learning. In this paper, we investigate a new sampling protocol, which draws samples in an online/exploratory fashion but allows one to backtrack and revisit previous states in a controlled and infrequent manner. We develop an algorithm tailored to this setting, achieving a sample complexity that scales practicallyly with the feature dimension, the horizon, and the inverse sub-optimality gap, but not the size of the state/action space.
  arXiv  Detail & Related papers  (2021-05-17T17:22:07Z)

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.