Research map / Bandits and online learning / RL theory and MDPs

Efficient Reinforcement Learning in Probabilistic Reward Machines

AAAI 2025 · Bandits and online learning › RL theory and MDPs · approach: Average-reward and latent MDPs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes UCBVI-PRM, a UCB-style model-based RL algorithm for MDPs with probabilistic reward machines achieving regret Õ(√(HOAT)+H²O²A^{3/2}+H√T), plus a non-Markovian simulation lemma giving reward-free exploration.

Problem

Regret minimization in episodic MDPs whose reward is non-Markovian and generated by a probabilistic reward machine (PRM), where existing methods either scale with the joint state space or only handle deterministic reward machines.

Approach

Exploit PRM structure by defining W_h over (PRM state, observation, action, next observation) so that the Bernstein bonus depends on observation-space quantities, yielding regret independent of the PRM state-space size; additionally a new simulation lemma for arbitrary non-Markovian rewards enables reward-free exploration.

Key results

• Regret bound Õ(√(HOAT)+H²O²A^{3/2}+H√T) for UCBVI-PRM, matching the Ω(√(HOAT)) lower bound when T ≥ H³O³A² and OA ≥ H, improving on UCRL2-RM's Õ(H√(OAT)) for DRMs.
• Reward-free exploration for any non-Markovian reward needs Õ(O⁵A³H²G²/ε²) episodes and yields an (ε+α)-optimal policy given an α-approximate planner.
• In RiverSwim and Warehouse experiments, UCBVI-PRM's regret grows slower than UCRL2-RM-L/B and the cross-product UCBVI baseline, with larger gaps for longer horizons and larger environments.

Measured effects reported in the paper

Limitations

• Regret lower-order term H²O²A^{3/2} and the sample complexity of reward-free exploration are worse than the Markovian case.
• Matching the lower bound requires T ≥ H³O³A² and OA ≥ H.
• Assumes known PRM structure; experiments only on small tabular grid environments.

Experimental setup

Datasets: RiverSwim (simulated MDP) Warehouse grid world (simulated PRM environment) Patrol DRM

Benchmarks: RiverSwim DRM environments (H=10/O=5, H=20/O=10, H=30/O=15) Warehouse PRM environments (3x3 H=9, 4x4 H=12, 5x5 H=15)

Metrics: cumulative regret over time

Baselines: UCRL2-RM-L UCRL2-RM-B UCBVI on cross-product MDP

Builds on: UCBVI UCRL2-RM EULER reward machines

Closest papers by meaning

• Reinforcement Learning with Stochastic Reward Machines (AAAI 2022 · similarity 0.91)
• Regret Bounds for Learning State Representations in Reinforcement Learning (NeurIPS 2019 · similarity 0.89)
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.89)
• IMED-RL: Regret optimal learning of ergodic Markov decision processes (NeurIPS 2022 · similarity 0.89)
• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.88)
• No-Regret Reinforcement Learning in Smooth MDPs (ICML 2024 · similarity 0.88)