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-world
applications, an interactive learning agent operates for a fixed or bounded
period of time, for example tutoring students for exams or handling customer
service requests. Such scenarios can often be better treated as episodic
fixed-horizon MDPs, for which only looser bounds on the sample complexity
exist. A natural notion of sample complexity in this setting is the number of
episodes required to guarantee a certain performance with high probability (PAC
guarantee). In this paper, we derive an upper PAC bound $\tilde
O(\frac{|\mathcal S|^2 |\mathcal A| H^2}{\epsilon^2} \ln\frac 1 \delta)$ and a
lower PAC bound $\tilde \Omega(\frac{|\mathcal S| |\mathcal A| H^2}{\epsilon^2}
\ln \frac 1 {\delta + c})$ that match up to log-terms and an additional linear
dependency on the number of states $|\mathcal S|$. The lower bound is the first
of its kind for this setting. Our upper bound leverages Bernstein's inequality
to improve on previous bounds for episodic finite-horizon MDPs which have a
time-horizon dependency of at least $H^3$.

本文研究了固定时间段内交互式学习智能体的表现，并从样本复杂度的角度提出了上下 PAC 确定性保证边界，为固定时间段内 MDP 的研究提供了理论上的支持。