- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The main claim of this paper is to provide a quantum algorithm that can improves both the time-dependent finite-horizon MDP and time-independent infinite-horizon MDP.
The techniques that the authors used are standard quantum tools like standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, as well as some enhanced value-iteration classical algorithms.
Critical strengths
The main strength of this paper is to provide a unified quantum algorithm to solve time-dependent finite horizon and time-independent infinite horizon MDA problems.
The paper requires expert in the area and the experts need to be well-versed in classical as well as quantum algorithms.
Critical weaknesses
The main drawback of this paper is that all the techniques used are indeed very standards quantum tools, and it is based one a classical classical (improved) MDP algorithms.
I tried to go through the main results, but the proofs are not easy to read, and there were a lot of "details' that the authors just skimmed over. So unless the authors provide more detail analysis and presentation, I am not sure whether the results are like what they claimed.
This paper improves the query complexity of obtaining epsilon-optimal policy (and potentially V-value functions) for time-dependent finite-horizon MDP. However, this improvement only exists for some time-independent infinite-horizon MDP (Notice that they pick up another factor of \Gamma). Besides, this improvement may be be extensible to obtaining Q-value functions. That is to say, the best quantum query complexity of obtaining Q-value functions remain as claimed by previous results. Therefore, the results of this paper is not as strong as it tried to claim.
Questions for authors
The proposed algorithm is really a "quantized" version of the standard value iteration. So there has to be a quantization errors and if one chooses a really small quantization error, what is the impact to the query complexity? This is not clear to me and this is an important issue.
This paper improves the query complexity of obtaining epsilon-optimal policy (and potentially V-value functions) for time-dependent finite-horizon MDP. However, this improvement only exists for some time-independent infinite-horizon MDP (Notice that they pick up another factor of \Gamma). Besides, this improvement may be be extensible to obtaining Q-value functions.
Can the authors show it detail how it can be extensible to other Q-value functions?
Also, please theoretically show the impact of .
Summary
We are a bit disappointed with the lack of engagement from the reviewers' side. Only one reviewer acknowledged our comments (by raising their score). It calls into question the need for a rebuttal period in the first place. Regardless, we summarise the two main complains from the reviewers and how we addressed them.
Two reviewers identified a potential bug in our proof. More precisely, a step in the algorithm can output (a superposition of) several good approximations instead of just one, which can be a problem for the subsequent step. We fixed this issue by employing a more elaborate subroutine than the old one. None of our results have changed due to this change.
One of our models focused on the time-independent setting and the third reviewer questioned about the time-dependent setting. Even though we have never seen a work, classical or quantum, address this setting, since it is a bit unusual for a few different reasons, we have properly extended the model to the time-dependent case. Contrary to what the reviewer thought, the complexities haven't gotten worse from this generalisation but have stayed exactly the same.
We hope this summary helps other reviewers and area chairs.