Pith. sign in

REVIEW 1 cited by

A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2310.12248 v3 pith:UDO7X7YG submitted 2023-10-18 cs.LG cs.LO

Mateo Perez , Fabio Somenzi , Ashutosh Trivedi This is my paper
classification cs.LGcs.LO
keywords algorithmobjectivesomega-regularlearningintroducemdpsapproximatelyconfirm
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

Linear temporal logic (LTL) and omega-regular objectives -- a superset of LTL -- have seen recent use as a way to express non-Markovian objectives in reinforcement learning. We introduce a model-based probably approximately correct (PAC) learning algorithm for omega-regular objectives in Markov decision processes (MDPs). As part of the development of our algorithm, we introduce the epsilon-recurrence time: a measure of the speed at which a policy converges to the satisfaction of the omega-regular objective in the limit. We prove that our algorithm only requires a polynomial number of samples in the relevant parameters, and perform experiments which confirm our theory.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality

    cs.LG 2026-05 unverdicted novelty 4.0 of 10

    Iterative refinement of unknown MDP parameters allows repeated satisfaction of PAC conditions, yielding asymptotic optimality for reachability specifications in RL.

Pith tools