Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs

Yes, you are correct that linear MDP implies $q_\pi$ realizability. However, $q_\pi$ realizability DOES NOT imply linear MDP, and one can show this via a counterexample. To name a few references that discuss this, please refer to Proposition 4 of Andrea Zanette et al., Learning near optimal policies with low inherent Bellman error, 2020a. (https://arxiv.org/pdf/2003.00153) and Hao, B et al., Confident least square value iteration with local access to a simulator (2022) (https://proceedings.mlr.press/v151/hao22a/hao22a.pdf).

Please note that our algorithm is NOT a straightforward extension of CAPI-QPI-Plan. Moreover, our paper distinguishes between the relaxed-feasibility and strict-feasibility problem settings. Treating each setting uniquely is a key strength of our work. In the relaxed-feasibility problem, the returned policy $\bar \pi_K$ is allowed to have some constraint violations, specifically where $v_{\bar \pi_K}^c(s_0) \geq b - \epsilon$. This contrasts with the strict-feasibility setting, where no constraint violations are permitted, meaning $v_{\bar \pi_K}^c(s_0) \geq b$. To address the strict-feasibility problem, the algorithm must solve a more conservative CMDP, as discussed in Section 6 of our paper. However, solving this more conservative CMDP incurs a higher sample complexity cost, necessitating that the relaxed-feasibility setting be treated separately. Additionally, in the presence of a misspecification error $\omega > 0$, the strict-feasibility setting requires additional assumptions on $\omega$, whereas the relaxed-feasibility setting does not. The sample complexity of the relaxed-feasibility setting can be independent of Slater's constant, whereas for strict feasibility, the returned policy must strictly adhere to constraints, and we cannot simply set Slater's constant $\zeta$ to $\epsilon$ and disregard its impact.

We are pleased to have addressed your concerns, and we sincerely thank the reviewer for their response.

You are correct that the mixture policy randomly selects an index $I \in {0, \ldots, K-1}$ with probability $1/K$ at deployment and then follows the policy $\pi_I$ for all subsequent steps. The value function of the mixture policy, $v_{\bar \pi_K}(s)$, is defined as the expected return when the mixture policy is initiated in state $s$: $v_{\bar \pi_K}(s) = \sum_{i=0}^{K-1} \text{Prob}(I = i) v_{\pi_i}(s) = \frac{1}{K} \sum_{i=0}^{K-1} v_{\pi_i}(s)$. This averaging of the value functions is used in our analysis to demonstrate that the returned mixture policy achieves the two feasibility objectives stated in sections 5 and 6.

It's important to note that the mixture policy is a history-dependent policy. The notation $\frac{1}{K}\sum_{k=0}^{K-1} \pi_k$ is defined with respect to trajectories. Specifically, this means that the probability of a trajectory is the weighted average of the probabilities of that trajectory under each of the component policies. We will also clarify this in the paper.

Question 2: The complexity guarantees has worse dependence on the effective horizon e.g. in Theorem 1 and in Theorem 2. Is this a consequence of the method or an artefact of the analysis? Can this be improved?

To address the strict-feasibility problem, the algorithm must solve a more conservative CMDP, as discussed in Section 6 of our paper. However, solving this conservative CMDP incurs a higher sample complexity cost, necessitating a separate treatment for the relaxed-feasibility setting. The worse dependence on the effective horizon is a consequence of the method. Improving the effective horizon terms in both settings remains an area of ongoing research.

Question 3: In Remark 3, the authors mention that the Slater's constant, which is required by their algorithm, can be approximated by another algorithm. Is this approximation trivial? How will the approximation error influence the current results?

Recall that Slater's constant is defined as $\zeta \doteq \max\_{\pi} v^{c}\_{\pi}(s_0) - b$. To approximate $\zeta$, one can run CAPI-QPI-Plan against the local-access simulator with constraint function $c$, treating it as an unconstrained problem optimizing with respect to only $c$. This algorithm yields an approximation of $\max_{\pi} v^{c}_{\pi}(s_0)$, which can then be used to calculate $\zeta$. We can run CAPI-QPI-Plan to obtain an approximate $\zeta$ before executing Confident-NPG-CMDP, and the sample complexity of CAPI-QPI-Plan is only additive to that of Confident-NPG-CMDP.

We will include the aforementioned elaboration on this remark in the paper.

Question 4.2: What is a suitable choice of $c$ and how does tuning this parameter show up in the performance guarantees?

We realized that the term $c$ was used in two different contexts, which may have caused some confusion. We used $c$ to denote both the constraint function and a user-defined parameter that bounds the importance sampling ratio in off-policy estimation, thereby determining the value of $m$. This overlap was an oversight on our part, and we will use two different notations to make the distinction in our paper. For the explanations that follow, we will refer to $c$ as the user-defined parameter that sets the value of $m$.

By setting $c$ to a value greater than 0 adjusts the resampling window, controlled by the quantity $m = O(\ln(1+c) \cdot \text{poly}(\epsilon^{-1} (1-\gamma)^{-1}))$, to ensure that the off-policy value estimators are well-controlled. As a result, $c$ appears in $L = \lfloor K / (\lfloor m \rfloor + 1) \rfloor$, where $L$ is the total number of data sampling phases. Additionally, $c$ appears in $n$, the number of roll-outs for each state-action pair in a core set. In the proof of Theorem 1 in Appendix C (page 29), we show that the algorithm will make $nH(L+1)|\mathcal{C}_0|$ queries to the simulator.

If $c > 0$, we see $L = \lfloor K / (\lfloor m \rfloor + 1) \rfloor \leq K/m \propto (1-\gamma)^{-3} \epsilon^{-1} (\ln(1+c))^{-1}$. All in all, we have $(1+c)^2/ \ln(1+c)$ showing up in the sample complexity. Since $c$ is a constant, we have omitted it from the tilde-big-O notation in the final sample complexity. In terms of $\epsilon$, with a factor of $\epsilon^{-2}$ contributed by $n$ and a factor of $\epsilon^{-1}$ contributed by $L$, we see that the total sample complexity is $\propto \epsilon^{-3}$.

If $c$ is set to 0, then $\ln(1+c) = 0$ and $m = 0$, reducing $L$ to $\lfloor K \rfloor$. In this case, the algorithm reverts to a purely on-policy approach and results in a sample complexity $\propto \epsilon^{-4}$. This motivated us to adopt the natural policy gradient and the off-policy approach to reduce the sample complexity from $\epsilon^{-4}$ to $\epsilon^{-3}$.

A similar analysis for the strict-feasibility setting can be found in Theorem 2 in Appendix D (page 31).

The overall memory requirement is $\tilde{d} n H L + \tilde{d} + L (m+1) \tilde{d} d$. The term $\tilde{d} n H L$ comes from maintaining $L+1$ copies of the core set $\mathcal{C}\_{l \in \\{0,...,L+1\\}}$, each containing no more than $\tilde{d}$ state-action pairs. For each state-action pair in $\mathcal{C}\_l$ for $l = 0,...,L$, the algorithm stores $n$ trajectories consisting of $H$ tuples $(s,a,r,c)$, requiring $\tilde{d} n H L$ memory. The additional $\tilde{d}$ accounts for the elements stored in $\mathcal{C}\_{L+1}$, which has no more than $\tilde{d}$ elements. In phase $L+1$, the algorithm terminates, so no roll-outs are required.

The term $L (m+1) \tilde{d} d$ arises from storing the least-squares weights of the estimator when a core set is extended. When a core set is extended (i.e., when discovered = true), the least-squares weights for the corresponding $m+1$ iterations are recalculated for the extended set on line 20 and stored for that extension. With a maximum of $\tilde{d}$ extensions per core set and $m+1$ corresponding iterations for each core set, and $L$ core sets in total, each weight vector of dimension $d$, this results in the $L (m+1) \tilde{d} d$ memory bound for storing the least-squares weights.

By substituting $n = \tilde{O}(\epsilon^{-2} (1-\gamma)^{-2})$, $H = \tilde{O}((1-\gamma)^{-1})$, $L = \tilde{O}((1-\gamma)^{-3} \epsilon^{-1})$, and $\tilde{d} = \tilde{O}(d)$, we obtain a total memory requirement of $\tilde{O}(d^2 \epsilon^{-3} (1-\gamma)^{-6})$.

Below, we provide a formal discussion on why and how we store the least-squares weights.

To return a mixture policy, the algorithm must access all policies $\pi_0,...,\pi_{K-1}$. Instead of storing the $\pi_k$ values for $k = 0,...,K-1$ across the entire state-action space, we store only the necessary information to reconstruct the policies when needed.

For a phase $l$, the policies $\pi_k$ for $k \in \\{ k_l+1, \dots, k_{l+1} -1 \\}$ depend on the core set $\mathcal{C}_l$. Since $\mathcal{C}_l$ can be extended multiple times during the algorithm, we track newly added states in each extension and store the corresponding least-squares weights. $\mathcal{C}_0$ can only be extended via line 12, and any other $\mathcal{C}_l$ (for $l = 1,...,L+1$) only via line 27, when the running phase $\ell = l-1$. Newly added elements are marked at lines 12 and 27. After lines 17-23 are executed, we store the least-squares weights associated with these newly added state-action pairs.

Using the tuples stored in $\mathcal{C}\_l$, along with the marking of which state-action pairs are newly added in each extension and their associated least-squares weights, we can reconstruct the policy $\pi_{k+1}$. For example, let $\mathcal{C}_l^1 = \emptyset$, and $\mathcal{C}_l^i$ denote all state-action pairs added to $\mathcal{C}_l$ in extension $i$. Let $w^i_k$ represent the least-squares weights computed using $\mathcal{C}_l^1 \cup \mathcal{C}_l^2 \cup \dots \cup \mathcal{C}_l^i$ for the $k$-th iteration. When $\mathcal{C}_l$ is extended for the $(i+1)$-th time, let $\mathcal{C}_l^{i+1}$ be the newly added pairs, making the latest $\mathcal{C}\_l = \mathcal{C}\_l^1 \cup \mathcal{C}\_l^2 \cup \dots \cup \mathcal{C}\_l^{i+1}$. The least-squares weight $w^{i+1}\_k$ is then computed using $\mathcal{C}\_l$. When line 25 of algorithm 2 (pg 12) is executed, $\pi\_{k+1}$ remains unchanged for states already in $\text{Cov}(\mathcal{C}\_l^1 \cup \dots \cup \mathcal{C}\_l^i)$, equivalent to $\text{Cov}(\mathcal{C}\_{l+1})$ in line 25, because line 27 would have been executed in the previous extension $i$ making $\mathcal{C}\_{l+1} = \mathcal{C}\_l^1 \cup \dots \cup \mathcal{C}\_l^i$. For states in $\text{Cov}(\mathcal{C}\_l^1 \cup \dots \cup \mathcal{C}\_l^{i+1}) \setminus \text{Cov}(\mathcal{C}\_l^1 \cup \dots \cup \mathcal{C}\_l^i)$ (equivalent to $\text{Cov}(\mathcal{C}\_l) \setminus \text{Cov}(\mathcal{C}\_{l+1})$ in line 25), $\pi\_{k+1}$ makes an NPG update using $w^{i+1}\_k$. For all other states not in $\text{Cov}(\mathcal{C}\_l)$, the policy remains as $\pi_k$.

A subroutine can perform these computations and return $\pi_{k}(\cdot | s)$ for any $s$ and $k$. By tracking newly added elements and the corresponding least-squares weights, the algorithm can reconstruct policies throughout its execution. From the stored data, the algorithm will have access to the constructed policies $\pi_0, \dots, \pi_{K-1}$ and return the value of a mixture policy when required.

We plan to add this discussion to the appendix in the final version of our paper.

We are pleased to have addressed your concerns, and we sincerely thank the reviewer for their thoughtful questions.