# Doubly-Asynchronous Value Iteration: Making Value Iteration Asynchronous in Actions

arXiv: https://arxiv.org/abs/2207.01613 · HTML: https://mlsanity.com/paper/2207.01613/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 4 Jul 2022.

## Builds on (most cited first, 6 of 6)

- [Learning and Planning in Complex Action Spaces](https://mlsanity.com/paper/2104.06303/) (2021)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [Planning by Prioritized Sweeping with Small Backups](https://mlsanity.com/paper/1301.2343/) (2013)
- [Lower Bound On the Computational Complexity of Discounted Markov Decision Problems](https://mlsanity.com/paper/1705.07312/) (2017)
- [AsyncQVI: Asynchronous-Parallel Q-Value Iteration for Discounted Markov Decision Processes with Near-Optimal Sample Complexity](https://mlsanity.com/paper/1812.00885/) (2018)
- [Marginal Utility for Planning in Continuous or Large Discrete Action Spaces](https://mlsanity.com/paper/2006.06054/) (2020)

## Built on by (most cited first, 2 of 2)

- [Learning in complex action spaces without policy gradients](https://mlsanity.com/paper/2410.06317/) (2024)
- [The Surprising Effectiveness of Approximate Value Iteration in Self-Play](https://mlsanity.com/paper/2609.09094/) (2026)

## Abstract (arXiv)

Value iteration (VI) is a foundational dynamic programming method, important for learning and planning in optimal control and reinforcement learning. VI proceeds in batches, where the update to the value of each state must be completed before the next batch of updates can begin. Completing a single batch is prohibitively expensive if the state space is large, rendering VI impractical for many applications. Asynchronous VI helps to address the large state space problem by updating one state at a time, in-place and in an arbitrary order. However, Asynchronous VI still requires a maximization over the entire action space, making it impractical for domains with large action space. To address this issue, we propose doubly-asynchronous value iteration (DAVI), a new algorithm that generalizes the idea of asynchrony from states to states and actions. More concretely, DAVI maximizes over a sampled subset of actions that can be of any user-defined size. This simple approach of using sampling to reduce computation maintains similarly appealing theoretical properties to VI without the need to wait for a full sweep through the entire action space in each update. In this paper, we show DAVI converges to the optimal value function with probability one, converges at a near-geometric rate with probability 1-delta, and returns a near-optimal policy in computation time that nearly matches a previously established bound for VI. We also empirically demonstrate DAVI's effectiveness in several experiments.