%ACambridge Yang%AMichael Littman%AMichael Carbin%D2023%I
%K
%MOSTI ID: 10404354
%PMedium: X
%TComputably Continuous Reinforcement-Learning Objectives are PAC-learnable
%XIn reinforcement learning, the classic objectives of maximizing discounted
and finite-horizon cumulative rewards are PAC-learnable: There are algorithms
that learn a near-optimal policy with high probability using a finite amount of
samples and computation. In recent years, researchers have introduced
objectives and corresponding reinforcement-learning algorithms beyond the
classic cumulative rewards, such as objectives specified as linear temporal
logic formulas. However, questions about the PAC-learnability of these new
objectives have remained open.
This work demonstrates the PAC-learnability of general reinforcement-learning
objectives through sufficient conditions for PAC-learnability in two analysis
settings. In particular, for the analysis that considers only sample
complexity, we prove that if an objective given as an oracle is uniformly
continuous, then it is PAC-learnable. Further, for the analysis that considers
computational complexity, we prove that if an objective is computable, then it
is PAC-learnable. In other words, if a procedure computes successive
approximations of the objective's value, then the objective is PAC-learnable.
We give three applications of our condition on objectives from the literature
with previously unknown PAC-learnability and prove that these objectives are
PAC-learnable. Overall, our result helps verify existing objectives'
PAC-learnability. Also, as some studied objectives that are not uniformly
continuous have been shown to be not PAC-learnable, our results could guide the
design of new PAC-learnable objectives.