Research map / Reinforcement learning / MDPs and planning
Periodic agent-state based Q-learning for POMDPs
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 PASQL, a periodic variant of agent-state Q-learning for POMDPs that learns L-periodic policies, proves convergence to a cyclic limit, and bounds the sub-optimality gap relative to history-dependent policies.
Problem
Agent-state based Q-learning in POMDPs learns stationary policies, but agent states (frame stacking, RNN states) are not Markov, so restricting to stationary policies can lose optimality.
Approach
Replace the single Q-function of agent-state Q-learning with an L-tuple of Q-functions updated periodically, so the learned policy is periodic with period L; convergence is analysed via time-periodic Markov chains and stochastic approximation, showing the limit depends on the behavior policy.
Key results
- On the constructed POMDP with gamma=0.9, the best period-2 deterministic policy achieves J=6.793 while the best stationary deterministic policy achieves J=2.633.
- For the deterministic example, the belief-based optimum is 10 versus 4.022 for the best stationary deterministic agent-state policy, and the periodic brute-force values approach larger values as period increases (e.g., 9.607 at L=9).
- PASQL iterates converge close to the theoretical limit predicted by the periodic MDP fixed point over 25 random seeds for three behavior policies.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| learn a periodic policy with period 2 instead of a stationary policy | agent-state Q-learning on the illustrative POMDP · Illustrative POMDP | best deterministic policy discounted return: 2.633 -> 6.793 | Helped |
| use behavioral policy μ₁ for PASQL | PASQL · Illustrative POMDP, period 2 | discounted return: 1.064 -> 6.793 | Helped |
| use behavioral policy μ₃ instead of μ₁ | PASQL · Illustrative POMDP, period 2 | discounted return: 6.793 -> 0.532 | Hurt |
| use behavioral policy μ₂ instead of μ̄₂ | periodic versus stationary agent-state Q-learning · Illustrative POMDP | discounted return: 1.064 -> 1.064; 2.633 -> 0.532 | Mixed |
| use a periodic deterministic policy with period 3 rather than period 1 | deterministic agent-state policy · Illustrative POMDP | discounted return: 4.022 -> 7.479 | Helped |
| increase the policy period from 3 to 4 | optimal deterministic agent-state policy · Illustrative POMDP | discounted return: 7.479 -> 6.184 | Hurt |
| use periodic behavior policy μ₂, which is aperiodic | PASQL · Illustrative POMDP, period 2 | time variation of learned Q-functions | Hurt |
Surprising findings
- The limit of PASQL depends on the behavior policy; a poorly chosen periodic behavior policy (mu_3) yields a converged policy with return 0.532, worse than stationary ASQL with a nominal behavior policy.
- Optimal periodic performance is not monotone in the period L (e.g., J*_5=8.810 > J*_6=7.479).
Limitations
- Analysis restricted to tabular off-policy Q-learning with a fixed periodic behavior policy; does not cover epsilon-greedy, SARSA, or function approximation.
- Converged policy depends on the behavior policy, and good behavior policies are hard to identify.
- Sub-optimality bound is relative to the optimal history-dependent policy and does not vanish as L grows.
Experimental setup
Benchmarks: custom 6-state POMDP example deterministic non-stationary POMDP example T-shaped grid world (analysis)
Metrics: Q-function convergence to theoretical limit discounted return of converged policy
Baselines: ASQL (stationary agent-state Q-learning, L=1) best stationary deterministic agent-state policy belief-based policy
Builds on: Q-learning agent-state Q-learning (ASQL) approximate information state periodic Markov chains
Closest papers by meaning
- Scalable Policy-Based RL Algorithms for POMDPs (NeurIPS 2025 · similarity 0.89)
- A PAC Learning Algorithm for LTL and Omega-Regular Objectives in MDPs (AAAI 2024 · similarity 0.88)
- Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy (NeurIPS 2024 · similarity 0.87)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.87)
- Rethinking Transformers in Solving POMDPs (ICML 2024 · similarity 0.87)
- Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.