mlsanityData to 14 Oct 2026

Computably Continuous Reinforcement-Learning Objectives are PAC-learnable

arXiv 2303.05518 ↗First posted 9 Mar 2023cs.LG cs.AIcited by 13

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 27 of its 61 references that are in the map. First posted on arXiv 9 Mar 2023.

Builds on

27 of 61 references.

References · 27

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018DAGs with NO TEARS: Continuous Optimization for Structure Learningcited by 752
  3. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  4. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  5. 2019DAG-GNN: DAG Structure Learning with Graph Neural Networkscited by 331
  6. 2013Causal Discovery with Continuous Additive Noise Modelscited by 255
  7. 2019Gradient-Based Neural DAG Learningcited by 227
  8. 2019Learning Sparse Nonparametric DAGscited by 207
  9. 2013CAM: Causal additive models, high-dimensional order search and penalized regressioncited by 178
  10. 2022Bayesian Structure Learning with Generative Flow Networkscited by 153
  11. 2019Causal Discovery with Reinforcement Learningcited by 145
  12. 2021DiBS: Differentiable Bayesian Structure Learningcited by 106
15 more
  1. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  2. 2019Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guaranteescited by 77
  3. 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 75
  4. 2019Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learningcited by 75
  5. 2018Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specificationscited by 72
  6. 2020A Composable Specification Language for Reinforcement Learning Taskscited by 69
  7. 2017Environment-Independent Task Specifications via GLTLcited by 67
  8. 2021Ordering-Based Causal Discovery with Reinforcement Learningcited by 55
  9. 2014Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraintscited by 54
  10. 2014A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specificationscited by 49
  11. 2018Structural Agnostic Modeling: Adversarial Learning of Causal Graphscited by 48
  12. 2015Partition MCMC for inference on acyclic digraphscited by 33
  13. 2019PAC Statistical Model Checking for Markov Decision Processes and Stochastic Gamescited by 32
  14. 2019Ordering-Based Causal Structure Learning in the Presence of Latent Variablescited by 26
  15. 2021Efficient PAC Reinforcement Learning in Regular Decision Processescited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 8; 2025: 2; 2026: 2.

13 papers.

Sort:

By area:

  1. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspectivecited by 16
  2. 2024Scalable Differentiable Causal Discovery in the Presence of Latent Confounders with Skeleton Posterior (Extended Version)cited by 6
  3. 2023Tree Search in DAG Space with Model-based Reinforcement Learning for Causal Discoverycited by 3
  4. 2024BECAUSE: Bilinear Causal Representation for Generalizable Offline Model-based Reinforcement Learningcited by 3
  5. 2024Reinforcement Learning for Causal Discovery without Acyclicity Constraintscited by 3
  6. 2024Weakly-supervised causal discovery based on fuzzy knowledge and complex data complementaritycited by 2
  7. 2025Causality-informed Anomaly Detection in Partially Observable Sensor Networks: Moving beyond Correlationscited by 2
  8. 2024Introducing Diminutive Causal Structure into Graph Representation Learningcited by 1
  9. 2024Enabling Causal Discovery in Post-Nonlinear Models with Normalizing Flowscited by 1
  10. 2024Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guaranteescited by 1
  11. 2025Causal Discovery via Bayesian Optimizationcited by 1
  12. 2026Consistency evaluation of benchmarks used for causal discoverycited by 1
1 more
  1. 2026From topology learning to graph generation: A unifying perspectivecited by 0