Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes doubly-asynchronous value iteration (DAVI) that generalizes asynchrony from states to states and actions. The intuition behind DAVI is incremental maximization, where maximizing over a few actions could improve the value estimate for a certain state. DVAI maximizes over a sampled subset of actions of arbitrary size. DAVI is proved to converge to the optimal value function with probability one at a near-geometric rate with probability $1-\delta$. DAVI returns a near-optimal policy in computation time that nearly matches a previously established bound for VI.
strengths_and_weaknesses: Strength:
1. This paper studies one of the most widely studies dynamic programming algorithm: Value iteration (VI). 
2. The proposed DAVI generalizes the idea of asynchrony from states to states and actions.
3. The computational complexity bound for DAVI nearly match a previously established bound for VI and the convergence rate is nearly geometric rate.
4. DAVIS could converge to the optimal value function despite only maximizing over a subset of actions in each update.

Weakness:
I don't work in this field.
questions: I don't have any questions
limitations: I have not seen any limitations. This paper is mathematically sound with good intuition.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper introduces and analyzes DAVI. A variation of value iteration that selects both the state and the action of evaluated look ahead asynchronously. It provides proof of convergence and convergence rate analysis for the algorithm as well as its computation complexity.
strengths_and_weaknesses: The paper is technically very precise, thorough, and well-written. It introduces a nice extension to normal value iteration, which seems to be effective in some domains. The possibility of choosing only a subset of actions to evaluate, opens up a new direction of research regarding the action selection method. One can see this line of research as equivalent of search-control queue studies. 


One strange part of the paper was the emphasis on DAVI "nearly matching" computational complexity of VI. The whole promise of DAVI is to be computationally more efficient than VI, and such guarantee is not helping with establishing that. It is a nice result to have but the writing is too positive about it in my opinion. I know the complexity is for the worst-case scenario and the speed-up probably does not always happen, which leads to my second suggestion.

A possible improvement to the paper would be some analysis of the cases DAVI introduces a speed-up compared to traditional VI. The experiments suggest that the number of viable action in each state is a factor for a speed-up. I wonder if this could be formalize in the form of $Q^*$ values.

Overall, I think this is a solid paper.

questions: Does authors have any more concrete conjectures about the scenarios DAVI converges faster than VI?
limitations: The algorithm's performance is precisely bounded and compared to literature.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper propose a dynamic-programming method with finer granularity than predecessor. The proposed method iterate on sampled actions rather than on the entire action set as seen in traditional value iteration and asynchronous value iteration. The resulting algorithm is provided with tight bounds and convergence results, with clear line of future work.

strengths_and_weaknesses: While theoretical analysis is thorough, the empirical result could be improved in complexity. A more challenging (realistic?) environment could be employed for evaluation. In addition, the proposed method does reduce the complexity of the problem by much (as expected), the entire sampling process may still be “prohibitively expansive”, which is not ideal if paired with catastrophically forgetting networks.
The paper is well written and the theoretical foundation is solid. 
questions: Sampling distribution (state and action) may become a prominent influencer if employed empirically, would the sampling distribution be better guided with exploration techniques based on the maturity of action values? 

limitations: Limited empirical performance gain.
review_title: null

Meta-review: metareview: The paper proposes and analyzes a new asynchronous value iteration method, which extends asynchrony from states to states and actions.
The reviewers have found the paper technically sound and well executed and they agree that it deserves publication.
In preparing the final version of their paper, the authors are invited to consider the reviewers' comments.
confidence: Certain
Decision: Accept