The Sample Complexity of Teaching-by-Reinforcement on Q-Learning

Abstract

We study the sample complexity of teaching, termed as "teaching dimension" (TDim) in the literature, for the teaching-by-reinforcement paradigm, where the teacher guides the student through rewards. This is distinct from the teaching-by-demonstration paradigm motivated by robotics applications, where the teacher teaches by providing demonstrations of state/action trajectories. The teaching-by-reinforcement paradigm applies to a wider range of real-world settings where a demonstration is inconvenient, but has not been studied systematically. In this paper, we focus on a specific family of reinforcement learning algorithms, Q-learning, and characterize the TDim under different teachers with varying control power over the environment, and present matching optimal teaching algorithms. Our TDim results provide the minimum number of samples needed for reinforcement learning, and we discuss their connections to standard PAC-style RL sample complexity and teaching-by-demonstration sample complexity results. Our teaching algorithms have the potential to speed up RL agent learning in applications where a helpful teacher is available.

References in corpus (18)

• An Overview of Machine Teaching
• Iterative Machine Teaching
• Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction
• Data Poisoning Attacks against Online Learning
• Adversarial Attacks on Stochastic Bandits
• Policy Poisoning in Batch Reinforcement Learning and Control
• Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning
• Teaching Inverse Reinforcement Learners via Features and Demonstrations
• Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners
• Adaptive Reward-Poisoning Attacks against Reinforcement Learning
• Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraints
• Toward the Fundamental Limits of Imitation Learning
• Online Data Poisoning Attack
• Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models
• Machine Teaching of Active Sequential Learners
• Dynamic Teaching in Sequential Decision Making Environments
• An Optimal Control Approach to Sequential Machine Teaching
• Using Machine Teaching to Investigate Human Assumptions when Teaching Reinforcement Learners