• Classified by Topic • Classified by Publication Type • Sorted by Date • Sorted by First Author Last Name • Classified by Funding Source •
Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory.
Alexander Levine, Peter
Stone, and Amy Zhang.
In International Conference on Learning Representations, April 2025.
[PDF]1.1MB [slides.pdf]1.6MB [poster.pdf]3.4MB
In order to train agents that can quickly adapt to new objectives or rewardfunctions, efficient unsupervised representation learning in sequentialdecision-making environments can be important. Frameworks such as the ExogenousBlock Markov Decision Process (Ex-BMDP) have been proposed to formalize thisrepresentation-learning problem (Efroni et al., 2022b). In the Ex-BMDP framework,the agent's high-dimensional observations of the environment have two latentfactors: a controllable factor, which evolves deterministically within a smallstate space according to the agent's actions, and an exogenous factor, whichrepresents time-correlated noise, and can be highly complex. The goal of therepresentation learning problem is to learn an encoder that maps fromobservations into the controllable latent space, as well as the dynamics of thisspace. Efroni et al. (2022b) has shown that this is possible with a samplecomplexity that depends only on the size of the controllable latent space, andnot on the size of the noise factor. However, this prior work has focused on theepisodic setting, where the controllable latent state resets to a specific startstate after a finite horizon. By contrast, if the agent can only interact withthe environment in a single continuous trajectory, prior works have notestablished sample-complexity bounds. We propose STEEL, the first provablysample-efficient algorithm for learning the controllable dynamics of an Ex-BMDPfrom a single trajectory, in the function approximation setting. STEEL has asample complexity that depends only on the sizes of the controllable latent spaceand the encoder function class, and (at worst linearly) on the mixing time of theexogenous noise factor. We prove that STEEL is correct and sample-efficient, anddemonstrate STEEL on two toy problems. Code is available at:https://github.com/midi-lab/steel.
@InProceedings{alexander_levine_iclr_2025,
author = {Alexander Levine and Peter Stone and Amy Zhang},
title = {Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory},
booktitle = {International Conference on Learning Representations},
year = {2025},
month = {April},
location = {Singapore},
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.
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Sun Apr 20, 2025 16:22:47