@inproceedings{
lazzati2024how,
title={How does Inverse {RL} Scale to Large State Spaces? A Provably Efficient Approach},
author={Filippo Lazzati and Mirco Mutti and Alberto Maria Metelli},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=ZjgcYMkCmX}
}
In online Inverse Reinforcement Learning (IRL), the learner can collect samples about the dynamics of the environment to improve its
estimate of the reward function. Since IRL suffers from identifiability issues, many theoretical works on online IRL focus on estimating the entire set of rewards that explain the demonstrations, named the *feasible reward set*. However, none of the algorithms available in literature can scale to problems with large state spaces. In this paper, we focus on the online IRL problem in Linear Markov Decision
Processes (MDPs). We show that the structure offered by Linear MDPs is not sufficient for efficiently estimating the feasible set when the state space is large. As a consequence, we introduce the novel framework of *rewards compatibility*, which generalizes the notion of feasible set, and we develop CATY-IRL, a sample efficient algorithm whose complexity is independent of the size of the state space in Linear MDPs. When restricted to the tabular setting, we demonstrate that CATY-IRL is minimax optimal up to logarithmic factors. As a by-product, we show that Reward-Free Exploration (RFE) enjoys the same worst-case rate, improving over the state-of-the-art lower bound. Finally, we devise a unifying framework for IRL and RFE that may be of independent interest.
How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach
Filippo Lazzati Mirco Mutti Alberto Maria Metelli