- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper considers the problem of RL in finite-state POMDPs by using neural function approximation, with guarantees on the regret bound. The paper proposes a method for solving this problem, which learns a neural policy in a superstate MDP approximation of the POMDP, whose states correspond to truncated observation histories of a fixed finite length. The contributions of the paper are as follows. First, the paper establishes a new pointwise bound on the difference between the value functions of the POMDP and the superstate MDP approximation, under a filter stability assumption. Second, the paper considers a neural policy evaluation via TD learning in the superstate MDP, and establishes an error bound on the approximation which depends on the neural architecture size, sampling error, and the bound between the POMDP and the superstate MDP approximation. Third, by combining policy evaluation with policy mirror descent for policy updates, the paper obtains an algorithm for RL in finite-state POMDPs with sublinear regret bound (the bound is sublinear in the product of the number of TD iterations and the policy update iterations). The paper performs a small experiment on an 11-state POMDP where the algorithm is compared with Q-learning and actor-critic on the superstate MDP.
Critical strengths
-
Novel method with guaranteed regret bounds. The paper considers an important and challenging problem of RL in POMDPs, and provides a theoretical analysis on the regret bound in finite-state POMDPs. The analysis is nontrivial and the bounds appear to be sound, although I haven't checked the appendix in detail. However, the bounds do not appear to be practically useful, see Weakness 1 below.
-
Clarity. The paper is generally well written and easy to follow.
Critical weaknesses
-
Regret bound for the sum of all policy updates. My main concern about the paper is that, while guaranteed regret bound is in principle an appealing property, I do not find the bound in this work to be practically useful. The regret bound in Theorem 3 and Corollary 4 considers the sum of regrets for all policies learned over all policy update iterations. Usually, one is interested in the regret bound for the final policy only, not all intermediate policy that a method has learned throughout the training process. This is reflected in the fact that the regret bound increases with the number of training iterations, which would not be useful for reasoning about the final policy.
Moreover, the regret bound is sublinear in which is the product of the number of policy evaluation iterations and the number of policy update iterations. Again, this is not a useful metric for reasoning about the regret of the final policy. -
Experiments. Experimental evaluation is limited to one toy example, an 11-state POMDP. Moreover, although the paper puts a lot of emphasis on neural vs linear function approximations, existing baselines that use linear function approximation and provide bounds are not considered in the experiments.
Questions for authors
-
Why is regret bound computed as a sum of regrets over all policies learned in all policy update iterations? Would it be possible to adapt your analysis to obtain a tighter bound on the regret of the final policy only?
-
Did you experimentally compare your method with the prior work of (Cayci et al. 2024) or (Anjarlekar et al. 2025) that use linear function approximation?