Pith. sign in

REVIEW 4 cited by

REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating 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 1205.2661 v1 pith:NPBKI4QG submitted 2012-05-09 cs.LG

Peter L. Bartlett , Ambuj Tewari This is my paper · ORCID
classification cs.LG
keywords algorithmoptimalregretspanbiascommunicatingregularizationvector
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of ~O(HSpAT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

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

  1. Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs

    cs.LG 2025-06 conditional novelty 8.0 of 10

    The MVP algorithm achieves a gap-dependent variance-aware regret bound using a new conditional total variance measure, and a matching lower bound shows this variance dependence is necessary.

  2. Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee

    cs.LG 2025-08 reject novelty 6.0 of 10

    First claimed regret bound for non-stationary restless multi-armed bandits via per-arm sliding-window optimism, but it holds for a relaxed regret measure and the proof contains gaps.

  3. Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning

    cs.LG 2025-02 conditional novelty 6.0 of 10

    For kernel-based reward-free RL, a simple uncertainty-maximizing exploration algorithm with unbiased samples achieves sample complexity ~O((H^3/eps)^(2+2/(p-1))) for polynomial eigendecay kernels, with an H-factor cos...

  4. Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration

    cs.LG 2025-01 reject novelty 5.0 of 10

    Concurrent RLSVI with aggregated states is shown to have worst-case regret O~(K H^(5/2) Γ √N) and per-agent regret 1/√N, with an analogous infinite-horizon bound.

Pith tools