Regret-Free Reinforcement Learning for LTL Specifications

Mahmoud Salamati; Rupak Majumdar; Sadegh Soudjani

REVIEW 5 major objections 3 minor 25 references

Regret-Free Reinforcement Learning for LTL Specifications

T0 review · 5 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper gives the first regret-free online algorithm for learning LTL controllers on unknown finite MDPs, proving $O(\sqrt{K})$ regret.

desk verdict The reach-avoid regret bound is a solid, novel start, but the LTL extension's central theorem is not supported: the policy inside accepting MECs is never constrained to be accepting, so the O(√K) regret claim holds only for a reach-avoid surrogate, not for LTL satisfaction. read the letter →

arxiv 2411.12019 v2 pith:CJTPKVQD submitted 2024-11-18 cs.AI cs.LG

Rupak Majumdar , Mahmoud Salamati , Sadegh Soudjani This is my paper · ORCID

classification cs.AIcs.LG

keywords regret-freereinforcementlearningLTLsynthesisMarkovdecisionprocessesreach-avoidspecificationsintervalMDPoptimisticvalueiterationgraphidentificationfinite-timeguarantees

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that an agent can learn a controller for an unknown finite Markov decision process against linear temporal logic (LTL) specifications with a finite-time regret guarantee: after $K$ learning episodes, the accumulated gap from the optimal satisfaction probability is $O(\sqrt{K})$, so the average gap tends to zero. The guarantee is the first of its kind; earlier LTL reinforcement-learning algorithms only proved asymptotic convergence, which says nothing about how close the current policy is during learning. The paper's route is to reduce general LTL objectives to infinite-horizon reach-avoid problems via automata and graph identification, and to solve the reach-avoid core with an optimistic interval-MDP algorithm that resets from bad states and caps each episode with a deadline. If the proof is right, a designer can stop learning after finitely many episodes and certify how far the current policy is from optimal, with confidence at least $1-2\delta$.

What carries the argument

The engine is an interval MDP (iMDP): at each episode, all observed transitions are summarized as a confidence interval around the empirical transition probabilities, chosen so the true MDP lies inside with high probability. Extended value iteration then picks, within that interval set, the most optimistic MDP and its optimal reach-avoid policy, a standard optimism-in-the-face-of-uncertainty move. What makes the regret analysis work is a per-episode deadline $H_k$, defined as the smallest $n$ for which a substochastic hitting-time matrix raised to the $n$-th power has norm at most $k^{-1/q}$, together with a reset rule that sends any visit to a bad state back to the initial state. Long (slow) episodes whose deadline is exceeded turn out to be rare enough that their total contribution is sublinear, while short (fast) episodes contribute only through the confidence radii and a martingale term, giving the $O(\sqrt{K})$ total. For general LTL, a known minimum transition probability $p_{\min}$ makes the underlying graph learnable in polynomial time, and the graph reveals the maximal end components (MECs) of the product MDP, which are declared accepting or non-accepting and become the goal and bad sets of the reach-avoid reduction.

What would settle it

Construct an MDP whose only route to the goal is a single edge of transition probability $p_{\min}/2$, and run Algorithm 1 while feeding the algorithm $p_{\min}$ as the lower bound. If the normalized regret still vanished, the theorem would be contradicted, because the hitting-time bound $\Lambda$ relies on every useful transition having probability at least $p_{\min}^{|S|}$; with the smaller true probability, the number of slow episodes need not stay sublinear.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4.2 and Theorem 5.1: for reach-avoid (until) formulas on any finite MDP with unknown transitions, the ZeroReg algorithm (Algorithm 1) achieves regret $R(K)=O(\sqrt{K})$ with probability at least $1-2\delta$, and for general LTL formulas the automaton-based reduction (Algorithm 4, using a graph learner that assumes a known lower bound $p_{\min}$) achieves the same order of regret with probability at least $1-\delta$. Regret is the accumulated difference between the optimal satisfaction probability and the satisfaction probability of each learned policy. The proof also shows the longest episode grows only logarithmically with $K$, which is what makes the bound genuinely sublinear rather than a disguised $O(K)$. Consequently the normalized regret $R(K)/K$ tends to zero, so a user can stop learning once the normalized regret is below a chosen threshold and trust the current policy to be near-optimal with the stated confidence.

Load-bearing premise

The whole guarantee rests on knowing a positive lower bound $p_{\min}$ on every nonzero transition probability, plus knowing (or learning in advance) which maximal end components of the MDP cannot reach the goal; if either is missing, the stated $O(\sqrt{K})$ regret bound is not established.

Editorial extensions

If this is right

Reach-avoid synthesis on an unknown finite MDP can be stopped after finitely many episodes with a certified distance to optimal: once $R(K)/K < \varepsilon$, the average satisfaction probability is within $\varepsilon$ of optimal with confidence at least $1-2\delta$.
General LTL objectives inherit the same guarantee through the automaton product, provided the graph has been learned, so infinite-horizon temporal specifications become verifiable during the learning phase rather than only in the limit.
The algorithm works from a fixed initial state without a generative model, which matches control and robotics settings where arbitrary resets are impossible.
Non-communicating MDPs, including the product MDPs that arise from LTL automata, are handled explicitly, because the reset mechanism replaces the communicating-MDP assumption used by earlier UCRL-style algorithms.
The graph learned from $p_{\min}$ is independent of the LTL formula, so one graph-learning pass can be reused for many specifications on the same dynamics.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the proof uses only hitting-time bounds and resets, the same deadline-and-reset scheme is a plausible template for regret guarantees on other undiscounted objectives, such as mean-payoff and average-reward specifications, and on stochastic shortest path problems where the goal is reached almost surely.
The bound grows exponentially in the state count through the parameter $\Lambda$, so the practical reach of the guarantee is likely limited to small- or medium-sized MDPs even though the asymptotics in $K$ are strong; testing the observed gap against the theorem's constants on larger grids would reveal how much slack the analysis carries.
A direct empirical probe of the graph learner would be to run Algorithm 5 on MDPs whose minimum nonzero probability is exactly $p_{\min}$ and slightly above it, checking whether the sample-complexity bound is tight or whether the true required samples are far smaller.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the quick take: the paper's headline claim—sublinear regret for LTL synthesis—doesn't survive close reading of Section 5. The reach-avoid core is real and likely correct, but the LTL reduction has a load-bearing gap that the authors need to fix before the main theorem means what it says.

What's genuinely new: for reach-avoid (until) formulas on finite MDPs with unknown transitions, the paper gives the first O(√K) regret bound, using optimistic iMDP value iteration with deadlines and resets, and it handles non-communicating MDPs—an advance over Tarbouriech et al. and Fruit et al. The graph-learning preprocessing with pmin is a reasonable extra, and the experiments show fast practical convergence. The writing is mostly clear and the comparison to ω-PAC is fair.

The problem is Theorem 5.1. The reduction to reachability of accepting MECs is standard for values, but the algorithm never constrains the policy inside those MECs. EVI treats G× as absorbing and episodes stop on first visit, so transitions inside an accepting MEC are never sampled and the returned argmax policy is arbitrary. A tie-break can pick an action that stays in the MEC but never visits the Rabin set K_i (or leaves the AMEC), making the true LTL satisfaction probability zero while the reach-avoid value is one. Then per-episode regret is one and R(K)=K. Nothing in Alg. 4 or the proof of Thm. 5.1 replaces the EVI policy inside each AMEC with an accepting policy. This is fixable—standard MEC theory gives an accepting positional policy, and changing the policy only inside G× doesn't change reach-avoid probabilities—but as written the LTL claim is not established.

Three smaller soft spots. First, Lemma B.1 assumes B contains every non-goal MEC, but Problem 1 doesn't state that; without graph knowledge the user can't supply such a B, so Thm. 4.2 needs an extra assumption or a graph-learning preprocessing step. Second, the confidence bookkeeping in Thm. 4.2 seems to drop the δ/3 from Lemma 4.1; the union bound gives 1-7δ/3 unless the δ's are redefined. That's likely repairable but needs writing out. Third, the graph-learning pseudocode (Algs. 5/6) is rough and the bound leans on the external ω-PAC sample complexity; this part needs tighter presentation.

Bottom line: the reach-avoid result deserves a serious referee and likely publication after revision; the LTL theorem needs the AMEC policy fix plus proof-surgery on the union bound. I'd send it to review, but I'd expect major revision.

Referee Report

5 major / 3 minor

Summary. The paper proposes an online reinforcement learning algorithm for finite MDPs with unknown transition probabilities and LTL objectives, claiming the first regret-free (sublinear regret) guarantee. The core algorithm (Alg. 1) builds an interval MDP from observations, computes an optimistic reach-avoid policy via extended value iteration (Alg. 2), and executes it for an episode-specific deadline. The LTL extension (Alg. 4) learns the MDP graph (Alg. 5), builds the product with a DRA, identifies accepting and non-accepting MECs, and runs the reach-avoid algorithm on the product. Theorems 4.2 and 5.1 claim O(√K) regret with high probability.

Significance. If the claims were fully correct, this would be a significant advance: it would give the first finite-time, non-asymptotic regret guarantee for LTL policy synthesis in unknown finite MDPs, without requiring a generative model, and it would handle non-communicating product MDPs via a reset mechanism. The paper also supplies explicit confidence intervals, a polynomial graph-learning procedure under a known pmin, and an experimental comparison. However, the LTL reduction has a gap: the policy synthesized by the reach-avoid algorithm is not shown to be accepting inside accepting MECs, so the main theorem is not established as stated.

major comments (5)

[Section 5, Algorithm 4; Theorem 5.1] The reduction from LTL to reach-avoid establishes equality of optimal values, not equality of the EVI policy's reach-avoid probability with its LTL satisfaction probability. Algorithm 1 terminates on first visit to G×, so transitions of actions inside an accepting MEC are never constrained by data, and EVI (Algorithm 2) assigns value 1 to every state in G× and hence to every action available there. A concrete failure: take an AMEC with states g1, g2, g3 and Rabin pair K={g2}, with actions at g1 leading to g2 or g3, and at g3 a self-loop; both actions from g1 have optimistic reach-avoid value 1, but the policy that chooses the path to g3 and then self-loops forever has reach-avoid value 1 and LTL satisfaction probability 0. Thus per-episode regret can be 1 for all K, contradicting the O(√K) bound of Theorem 5.1. The algorithm must compute an accepting policy for each AMEC (one that stays in the AMEC and visits some Ki infinitely often with probability 1) and use it once G× is entered, and Theorem 5.1 must be proved for that composite policy.
[Algorithm 1; Section 4.2] The pseudocode does not reset the current state to sinit at the start of an episode; it only resets when st∈B. The proof in Section 4.2 repeatedly states that 'every episode starts at sinit', and the regret Δk = v*(sinit)−vk(sinit) is defined for a policy executed from sinit. If an episode ends by deadline at a state outside G∪B, the next episode continues from that state, so the executed trajectories do not match the probabilities vk(sinit), and the martingale arguments over episodes are not justified. Please either add an explicit reset st←sinit at the beginning of each episode in Algorithm 1, or revise the analysis to account for the actual continuation state.
[Lemma B.1 and Lemma 4.4] Lemma B.1's bound Λ requires that B contains every maximal end component whose intersection with G is empty. This is not an assumption of Problem 1, which only gives B as the Avoid states of the until formula, and it is not checked or enforced by Algorithm 1. If the MDP has a closed recurrent class disjoint from G and B, then from states in S\B there is no positive-probability guarantee of reaching G, and the hitting-time bound (21), hence the logarithmic bound on αK in Lemma 4.4, fails. The reach-avoid theorem must either assume this graph-dependent condition, or Algorithm 1 must first learn the MECs (e.g., using Algorithm 5) and enlarge B accordingly.
[Section B.6, proof of Theorem 4.2] The union bound in the proof of Theorem 4.2 combines the failure probabilities 5δ/6, δ/6, and δ from Lemmas 4.5–4.7, but does not include the δ/3 failure probability of Lemma 4.1 for the event E that the true MDP lies in every Mk. Lemmas 4.5 and 4.7 use the confidence interval (3), which is valid only on E. The proof should either condition on E and add δ/3 to the failure budget, or state explicitly where this δ/3 is already absorbed in the stated probabilities; as written, the claimed confidence 1−2δ does not follow.
[Appendix A, Algorithm 5] The graph-learning algorithm requires, for every s∈S\{sinit}, a policy under which s is reachable from sinit with positive probability. For states that are not reachable in the true MDP, no such policy exists, and the outer while loop 'while n(s,a)<n*' can never terminate because the target (s,a) is never visited. The sample-complexity theorem (Theorem A.2) and the algorithm need to handle unreachable states explicitly (e.g., by characterizing the reachable set first or by treating unreachable states as having no outgoing transitions), or the theorem needs an additional assumption that all states are reachable.

minor comments (3)

[Algorithm 5] The call to Reach in Algorithm 5 contains an empty argument: 'Reach(S, A, s, , δ, pmin)' should be 'Reach(S, A, s, δ, pmin)'.
[Figure 4 caption] The caption contains a typo: 'algorithcm' should be 'algorithm'.
[Lemma B.1 proof] The sentence 'This is ensured by Eq. (6)' is not a direct consequence of the displayed inequality, since Eq. (6) is only an upper bound on v*; the proof should make explicit that the optimistic MDP has value at least v*, so that the greedy policy has positive reachability probability in the optimistic model.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main technical claims are derived from explicit concentration bounds and external theorems, not from their own conclusions.

full rationale

The reach-avoid regret bound (Theorem 4.2) is derived from concrete concentration inequalities, an optimistic iMDP construction whose confidence event is Lemma 4.1, and a deadline H_k defined by the substochastic matrix in Eq. (7). No target quantity is fitted to data, and no quantity is defined in terms of the regret it is supposed to explain. The graph-learning subroutine (Alg. 5, Theorem A.2) imports its sample-complexity components from external sources (Voloshin et al. 2022 and Perez et al. 2024) that share no authors with the present paper, and none of those imports assumes the present paper's regret theorem. The LTL reduction in Section 5 uses the standard AMEC characterization of Rabin acceptance, which is not a self-referential definition. The main caveat is a soundness gap rather than circularity: inside an accepting MEC G× the policy produced by Alg. 2 is only optimizing a reach-avoid value with G× treated as absorbing, so a tie-breaking action that leaves the MEC could make the true LTL satisfaction probability zero while the reach-avoid value is one; the proof of Theorem 5.1 does not currently close that gap. However, no argument step reduces to its own input by construction, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on domain assumptions (finite MDP, known pmin, positive satisfiability) plus a standard LTL-to-reachability reduction and the external ω-PAC sample complexity theorem. No numbers are fitted to data; the only non-obvious assumption introduced inside the analysis is the completeness of the bad-state set B. No new physical or mathematical entities are postulated.

assumptions (5)

domain assumption The transition probabilities are bounded below by a known pmin in (0,1) for every nonzero transition.
Used in Alg. 1 input, Eq. (7) deadline, Lemma 4.4 via Λ, Eq. (17) graph learning, and Theorem A.2. Without it, the sample complexity and regret bounds are not stated.
ad hoc to paper B includes all maximal end components (MECs) that do not intersect the goal set G.
Lemma B.1 uses this to guarantee each state in S\B reaches G with probability at least pmin^|S|. It is not part of Problem 1 and requires graph knowledge.
domain assumption The MDP is finite state and finite action, and LTL specifications are satisfiable with positive probability.
State in Sec. 3; v*(sinit)>0 assumed WLOG.
standard math Standard reduction: maximum LTL satisfaction probability equals maximum probability of reaching an accepting MEC in the product with a deterministic Rabin automaton.
Invoked in Sec. 5 and Alg. 4; cited to Baier and Katoen 2008.
standard math ω-PAC sample complexity of Perez et al. 2024 applies to the reachability policy search in Algorithm 6.
Theorem A.2 borrows C1 bound from ω-PAC; if this bound has different assumptions, the graph-learning complexity may not transfer.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Regret-Free Reinforcement Learning for LTL Specifications." pith.science (2026). https://pith.science/paper/CJTPKVQD

@misc{pith2026241112019,
  author       = {Pith},
  title        = {Pith review of: Regret-Free Reinforcement Learning for LTL Specifications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CJTPKVQD}},
  note         = {Machine review of arXiv:2411.12019}
}

read the original abstract

Learning to control an unknown dynamical system with respect to high-level temporal specifications is an important problem in control theory. We present the first regret-free online algorithm for learning a controller for linear temporal logic (LTL) specifications for systems with unknown dynamics. We assume that the underlying (unknown) dynamics is modeled by a finite-state and action Markov decision process (MDP). Our core technical result is a regret-free learning algorithm for infinite-horizon reach-avoid problems on MDPs. For general LTL specifications, we show that the synthesis problem can be reduced to a reach-avoid problem once the graph structure is known. Additionally, we provide an algorithm for learning the graph structure, assuming knowledge of a minimum transition probability, which operates independently of the main regret-free algorithm. Our LTL controller synthesis algorithm provides sharp bounds on how close we are to achieving optimal behavior after a finite number of learning episodes. In contrast, previous algorithms for LTL synthesis only provide asymptotic guarantees, which give no insight into the transient performance during the learning phase.

Figures

Figures reproduced from arXiv: 2411.12019 by the authors.

**Figure 2.** Map of the gridworld example with l = 6. The blue and green cells define the initial state (sinit) and target state (G), respectively. The red cells correspond to walls. The objective of the agent is to reach G without hitting the walls [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗

**Figure 3.** Variations of the empirical normalized regret, [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Comparison of the empirical normalized regret between our proposed regret-free algorithm and the [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]

**Figure 5.** Figure 5: Variations of the computed deadline, Hk, when our proposed algorithm is applied to the gridworld example with l = 6 [PITH_FULL_IMAGE:figures/full_fig_p021_5.png]

**Figure 6.** Figure 6: Comparison of the theoretical sample complexities for our proposed algorithm and the [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 17 canonical work pages

[1]

Taming the monster: A fast and simple algorithm for contextual bandits

Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. Taming the monster: A fast and simple algorithm for contextual bandits. In Xing, E. P. and Jebara, T. (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp.\ 1638--1646, Bejing, China, 22--24 Jun 2014. PM...

work page 2014
[2]

A framework for transforming specifications in reinforcement learning

Alur, R., Bansal, S., Bastani, O., and Jothimurugan, K. A framework for transforming specifications in reinforcement learning. In Principles of Systems Design: Essays Dedicated to Thomas A. Henzinger on the Occasion of His 60th Birthday, pp.\ 604--624. Springer, 2022

work page 2022
[3]

and Ortner, R

Auer, P. and Ortner, R. Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning, pp.\ 49–56. The MIT Press, September 2007. ISBN 9780262256919. doi:10.7551/mitpress/7503.003.0011. URL http://dx.doi.org/10.7551/mitpress/7503.003.0011

work page doi:10.7551/mitpress/7503.003.0011 2007
[4]

Near-optimal regret bounds for reinforcement learning

Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008

2008
[5]

and Katoen, J.-P

Baier, C. and Katoen, J.-P. Principles of model checking. MIT press, 2008

work page 2008
[6]

K., Wang, Y., Zavlanos, M

Bozkurt, A. K., Wang, Y., Zavlanos, M. M., and Pajic, M. Model-free reinforcement learning for stochastic games with linear temporal logic objectives. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp.\ 10649–10655. IEEE Press, 2021. doi:10.1109/ICRA48506.2021.9561989. URL https://doi.org/10.1109/ICRA48506.2021.9561989

arXiv 2021
[7]

Reinforcement Learning Based Temporal Logic Control with Maximum Probabilistic Satisfaction

Cai, M., Xiao, S., Li, B., Li, Z., and Kan, Z. Reinforcement learning based temporal logic control with maximum probabilistic satisfaction. CoRR, abs/2010.06797, 2020. URL https://arxiv.org/abs/2010.06797

work page Pith review arXiv 2010
[8]

T., Klassen, T

Camacho, A., Icarte, R. T., Klassen, T. Q., Valenzano, R. A., and McIlraith, S. A. Ltl and beyond: Formal languages for reward function specification in reinforcement learning. In International Joint Conference on Artificial Intelligence, 2019

work page 2019

Show all 25 references

[9]

Unifying pac and regret: uniform pac bounds for episodic reinforcement learning

Dann, C., Lattimore, T., and Brunskill, E. Unifying pac and regret: uniform pac bounds for episodic reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, pp.\ 5717–5727, Red Hook, NY, USA, 2017. Curran As...

2017
[10]

Near optimal exploration-exploitation in non-communicating markov decision processes

Fruit, R., Pirotta, M., and Lazaric, A. Near optimal exploration-exploitation in non-communicating markov decision processes. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS'18, pp.\ 2998–3008, Red Hook, NY, USA, 2018. Curran ...

2018
[11]

and Topcu, U

Fu, J. and Topcu, U. Probably approximately correct MDP learning and control with temporal logic constraints. In Robotics: Science and Systems X, University of California, Berkeley, USA, July 12-16, 2014, 2014

2014
[12]

M., Perez, M., Schewe, S., Somenzi, F., Trivedi, A., and Wojtczak, D

Hahn, E. M., Perez, M., Schewe, S., Somenzi, F., Trivedi, A., and Wojtczak, D. Omega-regular objectives in model-free reinforcement learning. In Tools and Algorithms for the Construction and Analysis of Systems: 25th International Conference, TACAS 2019, Held as Part of the Eu...

2019
[13]

J., and Lee, I

Hasanbeig, M., Kantaros, Y., Abate, A., Kroening, D., Pappas, G. J., and Lee, I. Reinforcement learning for temporal logic control synthesis with probabilistic satisfaction guarantees. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp.\ 5338–5343. IEEE Press, 2019...

2019
[14]

T., Klassen, T

Icarte, R. T., Klassen, T. Q., Valenzano, R. A., and McIlraith, S. A. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning, 2018

2018
[15]

Translating omega-regular specifications to average objectives for model-free reinforcement learning

Kazemi, M., Perez, M., Somenzi, F., Soudjani, S., Trivedi, A., and Velasquez, A. Translating omega-regular specifications to average objectives for model-free reinforcement learning. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent System...

2022
[16]

and Singh, S

Kearns, M. and Singh, S. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49: 0 209--232, 2002. URL https://api.semanticscholar.org/CorpusID:2695116

2002
[17]

and Ramaswami, V

Latouche, G. and Ramaswami, V. Introduction to Matrix Analytic Methods in Stochastic Modeling. Society for Industrial and Applied Mathematics, 1999. doi:10.1137/1.9780898719734. URL https://epubs.siam.org/doi/abs/10.1137/1.9780898719734

1999 doi
[18]

Reinforcement learning of control policy for linear temporal logic specifications using limit-deterministic generalized büchi automata

Oura, R., Sakakibara, A., and Ushio, T. Reinforcement learning of control policy for linear temporal logic specifications using limit-deterministic generalized büchi automata. IEEE Control Systems Letters, 4 0 (3): 0 761–766, July 2020. ISSN 2475-1456. doi:10.1109/lcsys.2020.2...

2020
[19]

A PAC learning algorithm for LTL and omega-regular objectives in mdps

Perez, M., Somenzi, F., and Trivedi, A. A PAC learning algorithm for LTL and omega-regular objectives in mdps. CoRR, abs/2310.12248, 2023. doi:10.48550/ARXIV.2310.12248. URL https://doi.org/10.48550/arXiv.2310.12248

2023 doi arXiv
[20]

Near-optimal regret bounds for stochastic shortest path

Rosenberg, A., Cohen, A., Mansour, Y., and Kaplan, H. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pp.\ 8210--8219. PMLR, 2020

2020
[21]

Limit-deterministic b \"u chi automata for linear temporal logic

Sickert, S., Esparza, J., Jaax, S., and K r et \'i nsk \'y , J. Limit-deterministic b \"u chi automata for linear temporal logic. In Chaudhuri, S. and Farzan, A. (eds.), Computer Aided Verification, pp.\ 312--332, Cham, 2016. Springer International Publishing. ISBN 978-3-319-41540-6

2016
[22]

M., and Seeger, M

Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. W. Information-theoretic regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, 58 0 (5): 0 3250--3265, 2012. doi:10.1109/TIT.2011.2182033

2012
[23]

No-regret exploration in goal-oriented reinforcement learning

Tarbouriech, J., Garcelon, E., Valko, M., Pirotta, M., and Lazaric, A. No-regret exploration in goal-oriented reinforcement learning. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine ...

2020
[24]

M., Chaudhuri, S., and Yue, Y

Voloshin, C., Le, H. M., Chaudhuri, S., and Yue, Y. Policy optimization with linear temporal logic constraints. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, Novembe...

2022
[25]

On the (in) tractability of reinforcement learning for ltl objectives

Yang, C., Littman, M., and Carbin, M. On the (in) tractability of reinforcement learning for ltl objectives. arXiv preprint arXiv:2111.12679, 2021

2021 arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Taming the monster: A fast and simple algorithm for contextual bandits

Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. Taming the monster: A fast and simple algorithm for contextual bandits. In Xing, E. P. and Jebara, T. (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp.\ 1638--1646, Bejing, China, 22--24 Jun 2014. PM...

work page 2014

[2] [2]

A framework for transforming specifications in reinforcement learning

Alur, R., Bansal, S., Bastani, O., and Jothimurugan, K. A framework for transforming specifications in reinforcement learning. In Principles of Systems Design: Essays Dedicated to Thomas A. Henzinger on the Occasion of His 60th Birthday, pp.\ 604--624. Springer, 2022

work page 2022

[3] [3]

and Ortner, R

Auer, P. and Ortner, R. Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning, pp.\ 49–56. The MIT Press, September 2007. ISBN 9780262256919. doi:10.7551/mitpress/7503.003.0011. URL http://dx.doi.org/10.7551/mitpress/7503.003.0011

work page doi:10.7551/mitpress/7503.003.0011 2007

[4] [4]

Near-optimal regret bounds for reinforcement learning

Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008

2008

[5] [5]

and Katoen, J.-P

Baier, C. and Katoen, J.-P. Principles of model checking. MIT press, 2008

work page 2008

[6] [6]

K., Wang, Y., Zavlanos, M

Bozkurt, A. K., Wang, Y., Zavlanos, M. M., and Pajic, M. Model-free reinforcement learning for stochastic games with linear temporal logic objectives. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp.\ 10649–10655. IEEE Press, 2021. doi:10.1109/ICRA48506.2021.9561989. URL https://doi.org/10.1109/ICRA48506.2021.9561989

arXiv 2021

[7] [7]

Reinforcement Learning Based Temporal Logic Control with Maximum Probabilistic Satisfaction

Cai, M., Xiao, S., Li, B., Li, Z., and Kan, Z. Reinforcement learning based temporal logic control with maximum probabilistic satisfaction. CoRR, abs/2010.06797, 2020. URL https://arxiv.org/abs/2010.06797

work page Pith review arXiv 2010

[8] [8]

T., Klassen, T

Camacho, A., Icarte, R. T., Klassen, T. Q., Valenzano, R. A., and McIlraith, S. A. Ltl and beyond: Formal languages for reward function specification in reinforcement learning. In International Joint Conference on Artificial Intelligence, 2019

work page 2019