On the Theory of Reinforcement Learning with Once-per-Episode Feedback
arXiv:2105.14363
Abstract
We study a theory of reinforcement learning (RL) in which the learner receives binary feedback only once at the end of an episode. While this is an extreme test case for theory, it is also arguably more representative of real-world applications than the traditional requirement in RL practice that the learner receive feedback at every time step. Indeed, in many real-world applications of reinforcement learning, such as self-driving cars and robotics, it is easier to evaluate whether a learner's complete trajectory was either "good" or "bad," but harder to provide a reward signal at each step. To show that learning is possible in this more challenging setting, we study the case where trajectory labels are generated by an unknown parametric model, and provide a statistically and computationally efficient algorithm that achieves sublinear regret.
arXiv commentPublished at NeurIPS 2022
References in corpus (9)
- (More) Efficient Reinforcement Learning via Posterior Sampling
- Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
- On Lower Bounds for Regret in Reinforcement Learning
- Reward-Free Exploration for Reinforcement Learning
- Improved Optimistic Algorithms for Logistic Bandits
- Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
- On the Performance of Thompson Sampling on Logistic Bandits
- Dueling Posterior Sampling for Preference-Based Reinforcement Learning
- Online Markov Decision Processes with Aggregate Bandit Feedback