Computably Continuous Reinforcement-Learning Objectives are PAC-learnable

2023-03-09 · Cambridge Yang, Michael Littman, Michael Carbin

In 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.

📄 PDF Abstract BibTeX arXiv:2303.05518

Code (0)

등록된 구현이 없습니다.

Tasks

General Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Computable learning of natural hypothesis classes

2024-07-23 · Matthew Harrison-Trainor, Syed Akbari

This paper is about the recent notion of computably probably approximately correct learning, which lies between the statistical learning theory where there is no computational requirement on the learner and efficient PAC…

Learning Theory

Find a witness or shatter: the landscape of computable PAC learning

2023-02-06 · Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas, Tomasz Steifer

This paper contributes to the study of CPAC learnability -- a computable version of PAC learning -- by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is cont…

PAC learning

On the Computability of Robust PAC Learning

2024-06-14 · Pascale Gourdeau, Tosca Lechner, Ruth Urner

We initiate the study of computability requirements for adversarially robust learning. Adversarially robust PAC-type learnability is by now an established field of research. However, the effects of computability requirem…

PAC learning

On the (In)Tractability of Reinforcement Learning for LTL Objectives

2021-11-24 · Cambridge Yang, Michael Littman, Michael Carbin

In recent years, researchers have made significant progress in devising reinforcement-learning algorithms for optimizing linear temporal logic (LTL) objectives and LTL-like objectives. Despite these advancements, there a…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Reinforcement Learning with General LTL Objectives is Intractable

2021-11-21 · AAAI Workshop CLeaR 2022 2 · Cambridge Yang, Michael Littman, Michael Carbin