Summary
The paper explores RL in Infinite-horizon Ergodic Average-reward constrained
MDPs under general policy parametrization. In this setting, the authors propose
a primal-dual based policy gradient algorithm that simultaneously optimizes the
policy parameter and a constraint violation penalty term $\lambda$. They also
equip their method with techniques to address challenges due to the
average-reward MDP setup, constraints on the MDP and general policy
parametrization. They prove global convergence of their resulting method in
terms of the Lagrange function and from this derive bounds on the expected
regret as well as constraint violation. Furthermore, when the policy class is expressive enough to approximately contain an optimal policy of the constrained MDP so that the un-expressivity parameter $\varepsilon_{bias}$ is zero or negligibly small, the authors prove that the
expected average regret and constraint violation of their method decreases at a rate of $O(T^{-1/5})$.
Strengths
1. The authors consider the task of reinforcement learning
in average-reward constrained MDPs and propose novel techniques to address
underlying challenges.
2. This is a complete piece of work that explores provably
efficient RL in average reward constrained MDPs. Their claims are backed by
theoretical analysis, and they highlight the strength as well as weaknesses
of their work.
3. This submission is clearly written. The authors highlight
the required assumptions and adequately discuss the nature of most relevant
parameters.
4. This work significantly contributes to existing theory
on reinforcement learning when it is more desirable to optimize the average
return, rather than the typical discounted return, and in addition to
return optimization, the policy is required to adequately adhere to
additional constraints on the MDP.
Questions
1. In Lines 243-246, the authors claim that there are scenarios under
which the un-expressivity parameter $\varepsilon_{bias}$ is zero or
negligible. I could reason about this claim when $\pi^{\*}$ is an optimal
policy in the unconstrained MDP, but unsure that the same holds when
$\pi^{*}$ is an optimal policy in the constrained MDP (see Line 240). Can
the authors kindly provide exact pointers in the referenced
papers that verify this claim, or a proof in the appendix?
2. In Lines 323 and 324, the authors claim that the primal-dual approach to policy optimization
is known to give worse results than in the unconstrained version, even for
the discounted setting. Could this be related to the fact that the method is policy, rather than value based? In the offline setting, [1] takes a value-based primal-dual approach and their result implicitly highlights that the constrained setting may not be worse off than the unconstrained setting.
3. Can the authors kindly elaborate on the bias of single
trajectory-based estimations in this setting? Reference [13] in the paper seems to
achieve better performance even with this biased estimation strategy.
4. How strong is Assumption 5?
[1] Hong, K., \& Tewari, A. (2024). A Primal-Dual Algorithm for Offline
Constrained Reinforcement Learning with Low-Rank MDPs. arXiv preprint
arXiv:2402.04493.
**Comments**
1. Line 265 makes reference to equation 21 twice rather than the
expressions after lines 263 and 264.
2. Expectation is sometimes expressed without the parenthesis. For
example, see Equations 20, 22, as well as Lines 265, 266 e.t.c.
Limitations
None. This is a purely theory paper.