# Computably Continuous Reinforcement-Learning Objectives are PAC-learnable

arXiv: https://arxiv.org/abs/2303.05518 · HTML: https://mlsanity.com/paper/2303.05518/

## 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 (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [Gradient-Based Neural DAG Learning](https://mlsanity.com/paper/1906.02226/) (2019)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [Bayesian Structure Learning with Generative Flow Networks](https://mlsanity.com/paper/2202.13903/) (2022)
- [Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/1906.04477/) (2019)
- [DiBS: Differentiable Bayesian Structure Learning](https://mlsanity.com/paper/2105.11839/) (2021)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees](https://mlsanity.com/paper/1909.05304/) (2019)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning](https://mlsanity.com/paper/1909.07299/) (2019)
- [Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications](https://mlsanity.com/paper/1807.06333/) (2018)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [Ordering-Based Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/2105.06631/) (2021)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [Structural Agnostic Modeling: Adversarial Learning of Causal Graphs](https://mlsanity.com/paper/1803.04929/) (2018)
- [Partition MCMC for inference on acyclic digraphs](https://mlsanity.com/paper/1504.05006/) (2015)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Ordering-Based Causal Structure Learning in the Presence of Latent Variables](https://mlsanity.com/paper/1910.09014/) (2019)
- [Efficient PAC Reinforcement Learning in Regular Decision Processes](https://mlsanity.com/paper/2105.06784/) (2021)

## Built on by (most cited first, 13 of 13)

- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [Scalable Differentiable Causal Discovery in the Presence of Latent Confounders with Skeleton Posterior (Extended Version)](https://mlsanity.com/paper/2406.10537/) (2024)
- [Tree Search in DAG Space with Model-based Reinforcement Learning for Causal Discovery](https://mlsanity.com/paper/2310.13576/) (2023)
- [BECAUSE: Bilinear Causal Representation for Generalizable Offline Model-based Reinforcement Learning](https://mlsanity.com/paper/2407.10967/) (2024)
- [Reinforcement Learning for Causal Discovery without Acyclicity Constraints](https://mlsanity.com/paper/2408.13448/) (2024)
- [Weakly-supervised causal discovery based on fuzzy knowledge and complex data complementarity](https://mlsanity.com/paper/2405.08699/) (2024)
- [Causality-informed Anomaly Detection in Partially Observable Sensor Networks: Moving beyond Correlations](https://mlsanity.com/paper/2507.09742/) (2025)
- [Introducing Diminutive Causal Structure into Graph Representation Learning](https://mlsanity.com/paper/2406.08709/) (2024)
- [Enabling Causal Discovery in Post-Nonlinear Models with Normalizing Flows](https://mlsanity.com/paper/2407.04980/) (2024)
- [Interventional Causal Structure Discovery over Graphical Models with Convergence and Optimality Guarantees](https://mlsanity.com/paper/2408.04819/) (2024)
- [Causal Discovery via Bayesian Optimization](https://mlsanity.com/paper/2501.14997/) (2025)
- [Consistency evaluation of benchmarks used for causal discovery](https://mlsanity.com/paper/2606.01789/) (2026)
- [From topology learning to graph generation: A unifying perspective](https://mlsanity.com/paper/2609.02286/) (2026)

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