2005 · 234 citations · 15 references
BusinessAutonomous SystemsMachine LearningMarkov Decision ProcessesRoboticsExploration-exploitation TradeoffLearning From DemonstrationOptimal ControlReinforcement LearningReinforcement Learning FoundationsStochastic ControlApprenticeship LearningExplorationExploration In Reinforcement LearningFinite-state ProcessesLinear State-space SystemsMartingale TheoryOptimal PoliciesReinforcement Learning Theory
Reinforcement learning in unknown‑dynamics systems often relies on exploration policies, such as E3, which can be impractical for safety‑critical applications like autonomous helicopters. This work investigates apprenticeship learning where a teacher demonstration is available. The proposed algorithm achieves polynomial scaling in state count for finite MDPs and in state dimension for continuous linear systems, proven via a martingale construction over relative losses. The authors demonstrate that, given the initial demonstration, no explicit exploration is required and near‑optimal performance relative to the teacher can be achieved by repeatedly executing exploitation policies that maximize rewards.
We consider reinforcement learning in systems with unknown dynamics. Algorithms such as E3 (Kearns and Singh, 2002) learn near-optimal policies by using "exploration policies" to drive the system towards poorly modeled states, so as to encourage exploration. But this makes these algorithms impractical for many systems; for example, on an autonomous helicopter, overly aggressive exploration may well result in a crash. In this paper, we consider the apprenticeship learning setting in which a teacher demonstration of the task is available. We show that, given the initial demonstration, no explicit exploration is necessary, and we can attain near-optimal performance (compared to the teacher) simply by repeatedly executing "exploitation policies" that try to maximize rewards. In finite-state MDPs, our algorithm scales polynomially in the number of states; in continuous-state linear dynamical systems, it scales polynomially in the dimension of the state. These results are proved using a martingale construction over relative losses.
15
PE, P. Billingsley · Journal of the American Statistical Association · 1996 · 6.7K citations
Andrew G. Barto · IFAC Proceedings Volumes · 1998 · 3K citations
Apprenticeship learning via inverse reinforcement learning
Pieter Abbeel, Andrew Y. Ng · 2004 · 2.9K citations