Resolving Partial Observability in Decision Processes via the Lambda Discrepancy

Thank you for your feedback.

Mathematical presentation

• notations are very confusing
• The products of tensors are presented as regular matrix multiplications without specifying which dimensions are used in the multiplications
• many definitions are not precise, like effective policy over latent state
• indices are meaningless i,j,k,l,...

We have fixed the mathematical presentation in the paper to make it easier to follow. Specifically,

1. We changed the indices from $i,j,k,l,...$ to indices that indicate their domain, such as $a_1, o_1,$ and $s_1$.
2. We have clarified the contractions used in the proof of Appendix A. We kept the matrix multiplications written as-is because they make sense as long as one follows the following guideline, which we included in the original paper: in the main paper equations, each tensor contraction is a single contraction except in the products involving $R^{SA}$ and $T$ on the right hand side, which are double contractions. We also tried writing the contractions with dots, but decided this tensor notation offered the best compromise between clarity and succinctness.
3. The effective policy over latent state $\Pi^S$ is an $S \times S \times A$ representation of the matrix $\phi \pi$, where $\phi$ is the $S \times \Omega$ observation function, and $\pi$ is the $\Omega \times A$ observation policy. Formally, $\Pi^S_{s,s’,a} = \delta_{s,s’} \phi_{s,o} \pi_{o,a}$.

Value definitions

The value functions of partial observable problems generally depend on the agent's entire history. But in Section 3.1, the Q-function is given as a function of the observation and action without any justification. This observation-action Q-function may be some useful approximation, but it is used throughout the paper as the correct value estimation without any discussion.

The MC Q-function is indeed well defined, but it is distinct from the Q-function conditioned on the agent’s full history. We define $Q(\omega,a)$ in the usual way: the expected discounted return starting from observation $\omega$, taking action a, and following the current policy thereafter. This expectation averages over all possible agent histories consistent with reaching observation $\omega$. We do not claim that this is equivalent to either the state value function $Q(s,a)$ or the history value function $Q(h,a)$, but it is nevertheless “correct” in that MC is an unbiased estimator of $Q(\omega,a)$, whereas TD($\lambda$) is not, for any $\lambda < 1$.

Clarifying conditionals

Several variables of conditional probabilities like $Pr(s|\omega)$ are presented as given constants, but they are not provided by the observation model like $Pr(\omega|s)=O(\omega|s)$; the probability $Pr(s_t|\omega_t)$ depends on the policy and the time instant $t$ in general.

We now describe in Appendix A that $P(s|\omega)$ reflects the average of $P(s_t|\omega_t)$ over all timesteps, weighted by visitation probability and discounted by $\gamma$. This is a well-defined stationary quantity, and it can be computed as follows. First solve the system $Ax = b$ to find the discounted state occupancy counts $x = c(s)$, where $A = (I - \gamma (T^\pi)^\top)$ accounts for the policy-dependent state-to-state transition dynamics $T^\pi$, and $b = P_0$ is the initial state distribution over $s$. Then $P(s|\omega) \propto c(s) * P(\omega|s)$, so we can just multiply these terms together and renormalize.

We will release the code alongside the paper so that these and other such computations will be clear.

Clarifying bootstrapping

Below the first big equation in Appendix A, it is claimed that one can bootstrap by replacing the last line with a term with Q(ω_2,a_2) when n=2... the bootstrap does not seem to hold given the time-homogenous definition of the Q-function unless with further justification.

Yes, we did mean for all the latter terms in "$\dots$" to be included. We rewrote the equations to make this clearer. We agree that using the time-homogenous Q-function bootstrap as is given here results in a quantity not equal to $\mathbb{E}[G_n|ω_0,a_0]$; that corresponds to the fact that the Q-value estimates are biased. The Q-values are commonly used this way, and doing so does not invalidate the results.

Thank you for your feedback.

Complexity

While memory augmentation is shown to improve performance, it doesn't directly address the computational complexity of solving POMDPs.

The computational and sample complexity of computing the $\lambda$-discrepancy are asymptotically the same as computing either of the two Q functions. The algorithm we present is only intended to provide an initial demonstration of the concept; it is not intended to be optimal. Our paper is focused solely on showing (both theoretically and empirically) that minimizing the $\lambda$-discrepancy leads to useful memory functions. The approach is applicable to any POMDP for which we can obtain an accurate observation-based Q function, but obtaining such a Q function is the subject of a large body of work and is outside the scope of this paper.

Scalability

The efficiency of the proposed approach in more challenging POMDP scenarios is not fully explored.

$$

POMDPs are hard to solve due to the large space of the belief states, and thus the algorithms are usually computationally and time-inefficient. However, the complexity of the algorithms is not discussed

(See "Scalability concerns" above.)

Single-$\lambda$?

It is still not clear to me why we need to reduce the $\lambda$-discrepancy, and at least an improved result should be shown by using this technique compared to using a single $\lambda$.

We are not aware of any method that can learn a memory function from a fixed TD($\lambda$) value function. TD($\lambda$) implicitly makes a Markov assumption for all $\lambda<1$, but there is no way to determine from a single value function whether the Markov assumption is a reasonable one. This is precisely why we need the second $\lambda$. The discrepancy between value functions reliably reveals partial observability and allows us to find a memory function that corrects for it.

Baselines

no baselines are included in the experiments.

(See "Comparisons to baselines" above.)

Partial/Full Information

Does the algorithm require the full information of the POMDP? If so, we can get the optimal solution with a POMDP solver.

No, we do not require the full information of the POMDP. The lambda discrepancy can be constructed only from observable quantities. Our method does not require the use of any environment information, not even knowledge of the complete set of states, let alone the current one. By contrast, belief-state planning methods require an accurate model of the transition dynamics, rewards, observation function, and the full set of states over which the belief has its support. Moreover, belief-state methods assume the agent has enough memory capacity to fully distinguish all possible belief states from each other, whereas our method is effective for limited-memory agents as well. This is why we normalize our performance results for each domain relative to the range from a uniform random policy (y=0) and the unrealistic POMDP-solver solution (y=1).

We only use the environment model in Section 4.2 to show that descending the gradient of the lambda discrepancy leads to useful memory functions. In Section 4.3 we show that using only accurate point estimates of the value function to minimize $\lambda$-discrepancy is as effective as using the environment model to find gradients.

Necessary Condition?

The condition in Lemma 2 is a sufficient condition; can a necessary condition be provided? That may help in designing the memory function.

Yes, we have the following necessary condition: Given a fixed policy and $λ_1$, $λ_2$ values, for almost all discount factor values $\gamma$, the converse holds, namely the condition in Lemma 2 implies that there is zero $\lambda$-discrepancy. We have added this to the updated paper, and included the proof in Appendix D.

Approximation

It seems that you approximate Equation (7) with Equation (10), what is the justification for that?

Thank you for bringing this up. The approximation was not central to any of the claims in the paper, so we have since removed Equation (10) from the work and replaced all experimental results that used the approximation with results computed exactly, following Equation (7). This only affected the results for the gradient-based optimization in Section 4.2, and the new results match or exceed the previous performance.

Thank you for your feedback.

Baselines

The experiment section is lacking, only comparing against a memory-free baseline

(See "Comparisons to baselines" above.)

Scalability

The tested environments and models are very low dimensional, and it's not clear such a method would scale to more interesting problems.

(See "Scalability concerns" above.)

TD Error

I do not see how $\lambda$-discrepancy is a better metric of Markovness than the traditional TD(0) Q learning error.

$$

What makes the $\lambda$-discrepancy specific to partial observability? A policy trained on a fully-observable MDP will also have a $lambda$-discrepancy if the Q function is even slightly less-than-optimal.

In POMDPs, value error comes from two places: estimation error (as in MDPs) and partial observability. Any method that estimates a value function will have some estimation error, and good value estimation approaches will hopefully drive this error to zero over time. The results we present here show that even if we achieve zero estimation error (which is the case for our value function oracle), there would still be error due to partial observability. Whereas Bellman error is currently the main method we use to reduce the former, it does nothing to reduce the latter. Using the $\lambda$-discrepancy, we are able to reduce the error due to partial observability.

To provide further evidence of this, we show in Appendix F that $\lambda$-discrepancy is positively correlated with value error in every domain we considered.

Thank you for your feedback, both here and for our previous submission. We agree that this version of the paper is a substantial improvement over the previous draft, and we are grateful for the role that your comments played in making that happen.

Scalability

I am a bit concerned with the scalability of the proposed method.

(See "Scalability concerns" above.)

Gradients

The empirical results do not include a gradient-based method for model-free implementation of $\lambda$-discrepency. I wonder if the authors would like to discuss the concrete challenges they met in such experiments.

There are a few potential ways to scale this up, and gradient-based methods are one example. As you saw in our previous draft, the $\lambda$-discrepancy can be computed using neural networks, which means that with the proper architecture, we can learn memory functions model-free via gradient descent. The experiments in our previous draft showed some initial success, but we decided to remove them from this version to focus purely on the tabular setting. We still believe that the neural network direction has promise, but we wanted the first paper on the $\lambda$-discrepancy to tell a theory-driven story. We felt that the engineering challenges associated with including neural networks warranted their own paper and were worried that they would overly complicate the story we are telling here.

Note that scaling up may also be possible gradient-free, via a policy-gradient-style approach; however, our initial investigation into this direction has revealed that this too would warrant its own separate paper, as the derivation is substantially more complicated here than for the MDP setting due to the lack of Markov property.

Hallway

In the previous version, the proposed method was shown to be struggling to acquire satisfying performances in two tasks. In this version, the authors have shown their success in one of them, Network. However, it seems the result of the other, Hallway, is omitted. I hope the authors would like to provide an explanation in their response.

The Hallway results included in the previous draft were misleading for a few reasons.

First, because the problem is too large for a closed-form POMDP solver, those results were instead normalized relative to the impossible standard of an optimal fully-observable state-based policy. We have since run the SARSOP solver, which does work and is a much more realistic comparison, but normalizing relative to multiple baseline algorithms further complicated the discussion.

Second, we found that the small improvement that we had previously achieved over the memoryless baseline was primarily due to the stochasticity introduced by the earlier stochastic form of memory functions we had investigated. Switching the policy optimization to policy gradient allowed us to better optimize over stochastic policies, and the memoryless policy achieves much better performance.

Third, once policy gradient revealed the optimal memoryless policy, it became clear to us that the Hallway domain simply does not benefit from the small amounts of memory we consider here. The domain involves highly-stochastic, agent-centric observations that must be integrated over multiple time steps, and then remembered across multiple stochastic state transitions, all while tracking more distinctions than are possible with such a small number of bits.