A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning
Inverse reinforcement learning (IRL) is the task of finding a reward function that generates a desired optimal policy for a given Markov Decision Process (MDP). This paper develops an information-theoretic lower bound for the sample complexity of the finite state, finite action IRL problem. A geometric construction of $\beta$-strict separable IRL problems using spherical codes is considered. Properties of the ensemble size as well as the Kullback-Leibler divergence between the generated trajectories are derived. The resulting ensemble is then used along with Fano's inequality to derive a sample complexity lower bound of $O(n \log n)$, where $n$ is the number of states in the MDP.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
An invitation to the sample complexity of quantum hypothesis testing
Quantum hypothesis testing (QHT) has been traditionally studied from the information-theoretic perspective, wherein one is interested in the optimal decay rate of error probabilities as a function of the number of sample…
LEMMATowards Theoretical Understanding of Inverse Reinforcement Learning
Inverse reinforcement learning (IRL) denotes a powerful family of algorithms for recovering a reward function justifying the behavior demonstrated by an expert agent. A well-known limitation of IRL is the ambiguity in th…
reinforcement-learningReinforcement LearningActive Exploration for Inverse Reinforcement Learning
Inverse Reinforcement Learning (IRL) is a powerful paradigm for inferring a reward function from expert demonstrations. Many IRL algorithms require a known transition model and sometimes even a known expert policy, or th…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
In this paper, we propose new problem-independent lower bounds on the sample complexity and regret in episodic MDPs, with a particular focus on the non-stationary case in which the transition kernel is allowed to change …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-worl…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)