Doubly-Asynchronous Value Iteration: Making Value Iteration Asynchronous in Actions
Authors: Tian Tian
Kenny John Young
Richard S. Sutton
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement learning
dynamic programming
planning

Abstract: 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.

Doubly-Asynchronous Value Iteration: Making Value Iteration Asynchronous in Actions
Tian Tian Kenny Young Richard S. Sutton
University of Alberta and Alberta Machine Intelligence Institute
Edmonton, Alberta, Canada
{ttian, kjyoung, reutton))Qullerta..co
Abstract
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 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 time, in mn-pacee and in 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, propose doubly- asynchronous value iteration (DAVI), a new algorithm that generalizes the idea asynchrony from states 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, show DAVI converges the optimal value function with probability one, converges at near geam-geomttric rate with probability 1 and returns near-optimal policy in computation time that nearly matches previously established bound for VI. We also empirically demonstrate DAVI's effectiveness in several experiments.
Introduction
Dynamic programming has been used to solve many important real-world problems, including but not limited wireless networks (Levorato et al., 2012; Liu al., 2017, 2019) resource allocation (Powell et al., 2002), and inventory problems (Bensoussan, 2011). Value iteration (VI) is a foundational dynamic programming algorithm central to learning and planning in optimal control and reinforcement learning.
VI of the most widely studied dynamic programming algorithm (Williams and Baird III, 1993; Bertsekas and Tsitsiklis, 1996; Puterman, 1994). VI starts from an arbitrary value function and proceeds by updating the value of all states in batches. The value estimate for each state in the state space must be computed before the next batch of updates will even begin:
e(s) + max ((ss,a) () + En(d'ss, a
for all s E S,
(1)
S'ES
where s' S is the next state, p(8'|s, a) is the transition probability, and r(s, is the reward. VI maintains two arrays of real values v. U. both the size of state space S = [S], with i being used to
make the update and being used to keep track of the updated values. In domains with large state
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

space, for example wireless networks where the state-space of the network scales exponentially in the number of nodes, computing single batch of state value updates using VI is prohibitively expensive, rendering VI impractical.
An alternative updating the state values in batches is to update the state values one at time, using the most recent state value estimates in the computation. Asynchronous value iteration (Williams and Baird III, 1993; Bertsekas and Tsitsiklis, 1996; Puterman, 1994) starts from an arbitrary value function and proceeds with in-place updates:
u(s,) f max aEA r(sn: (((mma)) +y +7
Ep(6)lsnna)u())) s'ES
where 8n S is the sampled state for update in iteration n with all other states 8 o 8n value remain the same.
Although Asynchronous VI helps to address domains with large state space, it still requires a sweep over the actions for every update due to the maximization operation over the look-ahead values: L"(s, a) r(s, a) + 7 E.'es p(s' s, as)( ) for a given v E RR. Evaluating the look-ahead values, as large the action space, can be prohibitively expensive in domains with large action space. For example, running Asynchronous VI would be impractical in fleet management, where the action set is exponential in the size of the fleet.
There have been numerous works that address the large action space problem. Szepesvári and Littman (1996) proposed an algorithm called sampled-max, which performs max operation over smaller subset of look-ahead values. Their algorithm resembles Q-learning, requiring a step-size parameter that needs additional tuning. However, their algorithm does not converge the optimal value function v² Williams and Baird III (1993) presented convergence analysis on a class of asynchronous algorithms,, including some that may help address the large action space problem. Hubert et al. (2021) and Danihelka et al. (2022) explore ways to achieve policy improvement while sampling only a subset of actions in Monte Carlo Tree Search. Ahmad al. (2020) focused the generation of smaller candidate action set to be used in planning with continuous action space.
We consider the setting where we have access to the underlying model of the environment and propose a variant of Asynchronous VI called doubly-asynchronean the idea of asynchrony from states to states and actions. Like Asynchronous VI, DAVI samples state for the update, eliminating the need to wait for all states to complete their update in batches. Unlike Asynchronous VI, DAVI samples subset of actions of any user-defined size via predefined sampling strategy. then computes only the look-ahcad values of the corresponding subset and a the computed values. The
value iteration (DAVI) that generalizes
best-so-far action, and updates the state value be the maximum intuition behind DAVI the idea of incremental maximization, where maximizing over a few actions could improve the value estimate for certain state, which helps evaluate other state-action pairs in subsequent back-ups. This simple approach of using sampling to reduce computation maintains similarly appealing theoretical properties to VI. In particular, we show DAVI converges v" with probability and at a near-geometric rate with probability - 5. Additionally, DAVI returns an e-optimal policy with probability 8 using
o (SSH, In SS /
11 9min
elementary operations, where is the size of the action subset, H,, is a horizon term, and Jmin the minimum probability that any state-action pair is sampled. We also provide a computational complexity bound for Asynchronous VI, which to the best of our knowledge, has not been previously reported. Our computational complexity bounds for both DAVI and Asynchronous VI nearly match previously established bound for VI (Littman et al., 1995). Finally, we demonstrate DAVI's effectiveness in several experiments.
Related work by Zeng et al. (2020) uses an incremental maximization mechanism that is similar to ours. However, their work focuses on a different setting from ours, an asynchronous parallel setting, where an algorithm is hosted on several different machines running concurrently without waiting for synchronization of the computations. Aside from this difference, their work considers the case where the agent has access to only generative model (Kearns et al., 2002) of the environment, whereas we assume full access to the transition dynamics and reward function. They also provided a computational complexity bound, which differs significantly from ours due to differences in settings.

---

2 Background
We consider discounted Markov Decision Process (S,A, p,,)) p) consisting of finite set of states S, a finite set of actions A, a stationary reward function : x A + [0, 1]. a stationary transition function p- S A S - [0, I]. and discount parameter y [0, 1). The stochastic transition between state s E S and the next state s' E S is the result of choosing an action a E A in For a particular s, a E probability, which we denote as p(s'|s. a).
A, the probability of landing in various s' is characterized by transition
For this paper, use II denote set of deterministic Markov polices { S A). The value function of a state evaluated according to π is defined as Uz (8) = 2 Oz | s] for E S. The optimal value function for state a deterministic optimal policy π for which the value function is v*. For the rest of the paper, we will consider y as vector of values of RR For fixed e O, a policy
is then e" (s) = max (s(s) and there exists
said to be e-optimal if Ux 2 0² - el. Finally, we will use || to denote infinity norm (i.e, ||l||| max, [o:] and A to denote the size of the action space.
3 Making value iteration asynchronous in actions
We assume access to the reward and transition probabilities of the environment. each iteration n, DAVI samples state 8n for the update and actions from the action set A. It then computes the corresponding look-ahead values of the sampled actions and the look-ahead value of a best-so-far action n. (s.). Finally, DAVI updates the state value the maximum over the computed look-ahead values. The size of the action subset can be any user-defined value between and A. To maintain a best-so-far action, one for every state amounts maintaining deterministic policy in every iteration. Recall (s, a) = r(s, a) + + + Eves p(s'), a)v(s") for given S A and v E R$, the pscudo-code for DAVI shown Algorithm
Algorithm 1: DAVI DAVI(m, p,
Input: State sampling distribution p E A(S)
Input: A potentially state conditional distribution over the sets of actions of size m denoted by
Input: Number of ittrations т, see Corollary for how to choose obtain e-optimal policy with high probability
Initialize the value function vp IRS
Initialize the policy To an arbitrary deterministic policy
for n = .............................. do
Sample state from p Sample m actions from q(118,) and be A.
Let a, = arg max. L (8, a) with ties broken randomly
Value back-up step:
Un+1 (s) max (L (8, a;) L mn (8))} if 8n otherwise
(s)
Policy improvement step:
ax
if = 8n and I (s, aii)) > L (8 (n (n))
10
(s)
(s)
otherwise
end
12
return Up:
Note that the policy will only change if there is another action in the newly sampled subset whose look-ahead value is strictly better than the current best-so-fit action's 's look-ahead value.
Convergence
We show in Theorem that DAVI converges to the optimal value function despite only maximizing over a subset of actions in each update. Before showing the proof, we establish some necessary definitions, lemmas, and assumptions.
3

---

Definition (gmin and Pmiin) Recall is distribution over states and is a potentially state conditional distribution over the sets of actions of size m. Then, we will use q(s, a) denote the joint probability that single state E S is sumpled for update with particular action included the set sampled by q. Furthermore, let Qmin mins, ((8, () and Pmin = min, p(8).
Definition 2 (Bellman optimality operator and policy evaluation) Let T R + R For all 8 E S, define Tu(s) = maxagA (8, a). Let T R - RR. For a given for all 8 E S, define (8)(8) = (8, π (8))-
Definition (DAVI back-up operator T,) Let Tn IRS RS. For a given An q. Tn E II, 8n E S, and for all E S and IRS, define
(( (s) for 8n (u(s)
Two(s)
(4)
otherwise.
We show in Appendix A that Tn is monotone operator.
Assumption (Initialization)
consider the following initialisations, (i) to 01, or (ii) vo c1 for c> 0, or (iii) (s(s) & [ (s, ro(s)) for all s S.
Lemma (Monotonicity) If DAVI is initialized according to (i).(ii), or (iii) of Assumption I, the value iterates of DAVI, (Un)a20 is a monotonically increasing sequence: Un S Un+1 for all n E No. if ifr(s, a) [0, for any 8, 8 A.
Proof: See Appendix A.
Lemma 2 (Boundedness (Williams and Baird III, 1993)) Let Umax = max, vo(s) and Umin min, (s) and recall that any reward E [0, 1]. If we start with any (Vo, To). then applying DAVI's operation the (vo; To) thereafter, will satisfy: min (0, Umin Vs(s) max { 1--7" Vmax for all E S and all n E No.
Lemma 3 (Fixed-point iteration (Szepesvári, 2010) Given any v E R$, and T, T,Ta defined in Definition 2
1. Un lim THU for a given policy æ. In particular for any n 2 ||T uzll S ~01 [| - Uzl where v, is the unique function that satisfies Tv = Ux.
2. V* limm- T and in particular for any n 2 0. -| - Tl S 22 e11. where 2*
is the unique function that satisfies Tu" =v-
Theorem (Convergence of DAVI) Assume that q(s, a) > O and r(s, a) E [0, for any a e A. then DAVI converges to the optimal value function with probability if DAVI initializes according to (i), or (ii)) of Assumption I.
Proof:
By the Monotonicity Lemma and Boundedness Lemma 2, DAVI's value iterates (Vn)a20 are bounded and monotonically increasing sequence. By the monotone convergence theorem, limm-+00 Up = sup,, Un = U. It remains to show that ē = v². We first show S o- and then show 0 o" to conclude that E v². We note that u, = - & T'n-1, where T is the Bellman optimality operator that satisfies the Fixed point Lemma (2). By the monotonicity of T and the monontonicity of vn 's, for any 2 0, en I T By taking the limit of co on both sides, we get < U*
Now, we show 2 v". Let (nx) be sequence of increasing indices, where ng = 0, such that between nigth and 1-th iteration, all state s have been updated at least once with an action set containing n" (s). We note that the number of iterations between any nı and 744+1 is finite with probability since there is finite number of states and actions, and all state-action pairs are sampled with non-zero probability. Then, for any state s, let t(s, k) be iteration index such that St(e.k)

---

n S t(s,k) I *++1, and xs(s) E A(s.)), then by monotonicity of On
Um2+: (8) 2 ((x
(5)
=max
max (F
I. (s, a), (s n (6)) 2 2I (8,
(6)
-Ta- -T- (s) 2 Uni (s) by monotonicity of the operator.
By the n1++1-th iteration, Pma+1 2 Ung, where T is the policy evaluation operator that satisfies
Ung, the exxed-point Lemma (I). Continuing with the same reasoning, Unu 2 Th vn for any k 2 By taking limit of l + oo on both sides, we get e 2 v². Altogether, ह = V²
Remark 1: The initialization requirement in the Convergence of DAVI Theorem can be relaxed to be any initialization, and DAVI will still converge to v" with probability 1. A more general proof can be found in Appendix A, which follows similar argument to that of the proof for Theorem 4.3.2 of Williams and Baird III (1993). Intuitively, there exists a finite sequence of value back-up and policy improvement operations that will lead to one contraction, and if there | NN copies of such sequence, this will lead to contractions. Once the value iterates contract into an "optimalit-ccattre" region, where all the policies na are optimal thereafter, DAVI is performing policy evaluations of an optimal policy. As long as all states are sampled infinitely often, the value iterates must converge v². Finally, we show that such finite sequence as contiguous subsequence exists in an infinite sequence of operators generated by stochastic process.
DAVI could be considered Asynchronous Policy Iteration algorithm (Bertsekas and Tsitsiklis, 1996) since DAVI consists of policy improvement step and a policy evaluation step. However, the algorithmic construct discussed by Bertsekas and Tsitsiklis (1996) does not exactly match that of DAVI with sampled action subsets. Consequently, we could not directly apply Proposition 2.5 of Bertsekas and Tsitsiklis (1996) to show DAVI's convergence. A more useful analysis is that of Williams and Baird III (1993); we could have applied their Theorem 4.2.6 to show DAVI's convergence after having shown that DAVI's value iterates are monotonically increasing in Lemma 1. However, Williams and Baird III (1993) provide no convergence rate or computational complexity. Therefore, we chose to present a different convergence proof, more closely related the convergence rate proof in the next section.
Remark 2:
5 Convergence rate
DAVI relies on sampling avoid sweeps through the state and action space, which introduces additional error. Despite this, we show in Theorem 2 that DAVI converges at a near-geometric rate and nearly matches the computational complexity of VI.
Theorem (Convergence rate of DAVI) Assume q(s, > and r(s, E 10 for any s, a e S x A. and also assume DAVI initialises according to (i), (ii), (üi) of Assumption 1. With y E [0, 1) and probability 5, the iterates of DAVI, (Wn)n20 converges to v" at a near-geometric rate. In particular, with probability 1 8, for a given I N,
||u" rall S 3/1lo* vall.
(8)
for any satisfying
St In
1 / In 1 Jmin ) 1
>
(9)
8
where Quin minl, aa a(s.a).
Proof: Recall from Lemma 1, we have shown 2n - V² monotonically from below. From Theorem 1, we have also defined (na ) to be sequence of increasing indices, where no O, such that between the ng and 1-th iteration, all state & E S have been updated at least once with an action set containing x =s)). At the 14+1-th iteration, Una Tu- This implies that at the
4441-th iteration, DAVI would have 7-contracted at least once:
0 f V² - Upe+i I 0² - TT Unz: = -|1" - Uns+il 1l S -100 Tnaunalls
(10)
||o" TT- = TT x Ta- S 7/10" - valll
(11)
||0* Unetil S "/|0* Unall.
(12)
5

---

Consider dividing n E N iterations into uniform intervals of length N such that the i-th interval is (iN, (i + 1)N - -1). Let (s) denote the event that at some iteration in the i-th interval, state has been updated with an action set containing x² (s). Therefore, an occurrence of event & = (() would mean that (i + 1)- iteration, P(++1)N would have contracted at least once. Then, on the event & = n&&; 0 S Es)), there have been at least / c-ootracction after n iterations.
We would like P(E) 2 1 - å or alternatively the probability of failure event P(E9) < 6, for some ò O. However, just how large should N be in order maintain a failure probability of 6? To answer this question, we first bound P(E)) using union bound:
P(E = P(U; USES Ef(s) S ΣV P(E
(13)
i=
From Definition 1, ((*)x*(s)) (s)) is the joint probability that single state s is sampled for update with x" (s) included in the action subset sampled by q. Then, the probability that state 8 is not updated with action set containing nr" (s) in N iterations is q(8, x² (s))) Continuing from (13),
P(E)) S Σ1a (1 (()) S SI(1 Imin)
(14)
SES
where Jmin = min,a ((8,a) a). Now set SI(1 - Qmin)) S ā and solve for N,
5
N 2 In
In Iminn)
(15)
S1
Thus, with probability at least - 8, within
SI
= 1 In
In
(16)
qmin
iterations DAVI will have 7-contracted least times.
Remark: We note that p, q could be non-stationary and potentially chosen adaptively based on current value estimates, which is interesting direction for future work.
Corollary (Computational complexity of obtaining e-optimal policy) Fix an E (0, l|u* voll), and assume DAVI initialises according to (i), (ii), or (iil) of Assumption Define
1100
voll
Hyye In
/1 11-7
(17)
as a horizon term. Then, DAVI runs for at least
T= Hyps In (SHlie (I((Stne))
/ In
(18)
Gmin
iterations, returns an e-optimal policy Tn Vnn 2 0- -1 with probability at least 1 - using O (mST) elementary arithmetic and logical operations, where m is the size of the action subset and S is the size of the state space. Note that ||l* - voll is unknown but it can be upper bounded by 1-y + ||ua]] given rewards are in [0, 1).
Proof: See Appendix A.
Remark: As straightforward consequence of Theorem I and Corollary 1, show in Appendix A (Corollary 2) that DAVI returns an optimal policy T- with probability 8 within a number of computations that depends on the minimal value gap between the optimal action and the second-best action with respect to v".
We can compare the computational complexity bound for DAVI (the result of Corollary 1) to similar bounds for Asynchronous VI and VI. As far as we know, computational complexity bounds for Asynchronous VI have not been reported in the literature. We followed similar argument to Theorem and Corollary I to obtain the computational complexity bound for Asynchronous VI in Appendix B.

---

Table I: Computational complexity of VI, Asynchronous VI, DAVI
Algorithms
Computational complexity
References
VI
0
ASS
H
Littman et al. (1995)
25
In
Asynchronous VI
O
Ti ASH
This paper
In
DAVI
mSH
This paper
To
Recall that Jmin ming,a ((s, a). Consider the case of uniform sampling of states and actions. Uni- form sampling of the states results in a probability of ş of sampling particular state, while uniform sampling of m actions without replacement results in a probability of in of including particular ac- 3A
tion in the subset. Altogether Qmin = in Uniform sampling of state and action subset is the best sam-
pling strategy for the bound O (mSH, In S
In (I-I....)
because any non-uniform m/
strategy would result in Juin < 9.1 Suppose Quin 3A then -m/ (In(1
m
SA. Therefore, DAVI's computational complexity O (m.lt [n SH
o S AH,,
[H ). Likewise, uniform sampling of state will result Pmin = 3 and
so follows that -1/ (In 5) (==))))) ))) ~ = OS In ($ T-pman))
S. Then, Asynchronous VI's computational complexity
O ASH In SH
Chen and Wang (2017) have established a lower bound on the computational complexity of planning in finite discounted MDP to be ()) The importance of their result shows that no algorithm escape this 52 A computational complexity. Both DAVI and Asynchronous VI computational complexity matches that of the lower-bound (2(5aA) A) up to log terms in $2 A but have additional dependence on H., and In(1/5).
VI, Asynchronous VI, and DAVI all include a horizon term. The horizon term Hy,e improves upon /(1 (11~7) that appears in the VI bound of Littman al. (1995) when 7 0.5. As VI does not require sampling, it has no failure probability, Thus, DAVI and Asynchronous VI both have an additional In (t). We leave open the question of whether the additional log term In(SH,,. in DAVI and Asynchronous VI necessary.
the horizon term of H. <(1-r) In (2ille- <(1>>)
2-
The computational complexity of DAVI nearly matches that of VI, but DAVI does not need to sweep through the action space in every state update. Similar to Asynchronous VI, DAVI also does not need to wait for all states to complete their update in batches, as is the case of VI, making DAVI more practical algorithm.
6 Experiments
DAVI relies sampling to reduce the computation of each update, and the performance of DAVI can affected by the sparsity of rewards. a problem like a needle in a haystack, where only one specific sequence of actions leads to reward, then we do not anticipate uniform sampling to be beneficial in terms of total computation. An algorithm would still have to consider most states and actions make progress in this case. On the other hand, hypothesize that DAVI would converge faster than Asynchronous VI in domains with multiple optimal or near-optimal policies. To isolate the effect of reward sparsity from the MDP structure, we first test hypothesis several single-state MDP domains. However, solving a multi-state MDP is generally more challenging than solving a single-state MDP. In second experiment, examine the performance of DAVI on two sets of MDPs: an MDP with a tree structure and a random MPD.
The algorithms that will be compared in the experiments are VI, Asynchronous VI, and DAVI. We implement Asynchronous VI and DAVI using uniform sampling to obtain the states. DAVI samples a new set of actions via uniform sampling without replacement in each iteration.
7

---

6.1 Single-state experiment
This experiment consists of single-state MDP with 10000 actions, all terminate immediately. We experiment two domains: weedle-inthe-hhasstack and multi-reward. Needle-in-the-hayeee has one random action selected to have a reward I, with all other rewards set O. Multi-reward has 10 random actions with a reward of 1. The problems in this single-state experiment amount to brute-force search for the actions with the largest reward.
6.2 Multi-state experiment
This experiment consists of two sets of MDPs. The first set consists of tree with depth of 2. Each state has 50 actions, where each action leads to 2 other distinct next states. All actions terminate at the leaf states. Rewards 0 everywhere except at random leaf state-action pair, where reward is set With this construct, there are around 10000 states. The second set consists of a random MDP with 100 states, where each state has 1000 actions. Each action leads 10 next states randomly selected from the 100 states with equal probability. All transitions have a 0.1 probability of terminating, A single state-action pair randomly chosen have a reward of 1. The y in all of the MDPs are 1.
6.3 Discussion
Figure and Figure 2 show the performance of the algorithms. All graphs included error bars showing the standard error of the mean. Notice that all graphs started at and eventually reached an asymptote unique each problem setting. All graphs smoothly increased towards the asymptote except for Asynchronous VI Figure and VI in Figure whose performances were step-functions 1 The y-axis of each graph showed state value averaged over 200 runs. The x-axes showed run-times, which have been adjusted for computations.
In Figure 1(a,b). DAVI with m = was significantly different from that of DAVI with m 10, 100, 1000, and DAVI with 10, 100, 1000 converged a similar rate. While Figure 2(a.b), all algorithms were significantly different. DAVI m 10 in random MDP Figure 2(b) converged faster than any other algorithms. These results suggest that an ideal m exists for each domain.
state value averaged over 200 runs
(a) needle-in-the-haystar
(b) multi-reward
1
Asynchronous VI
DAVI m=1
DAVI =10
DAVI m=100
DAVI m=1000
0
0
10,000
100,000
10,000
20,000
run-time #operations
run-time #operations
Figure 1: Single-state experiment with 10, 000 actions: (a) has only one action with a reward (b) has 10 actions with reward of 1. The Asynchronous VI in this experiment is equivalent to VI since there is only one state. We run each instance 200 times with new MDP generated each time. In each run, each algorithm is initialized to 0.
In the needle-in-ther thaull--n-the-hhystackkk setting Figure 1(a), all four DAVI algorithms made some progress by the 10000 computation mark while Asynchronous computing the look-ahead value for all of the actions, it reached the asymptote immediately. On the other hand, DAVI might have been lucky in some of the runs, found the optimal action amongst the subset early on, logged it as a best-so-far action, and had a state value sustained at 1 thereafter. However, there could also be runs where sampling had the opposite effect.
stayed flat. Once Asynchronous finished
Asychronous VI in the single-state experiment is equivalent VI since there only state.

---

Changing the reward structure by introducing few redundant optimal actions into the action space increased the probability that an optimal action was included in the subset. In the multi-reward setting Fig. (b), DAVI with all settings of m have essentially reached the asymptote by the 10000 mark. DAVI with all four action subset sizes reached the asymptote faster than Asynchronous VI. As expected, DAVI converged faster than Asynchronous VI in the case of multiple rewarding actions.
In the Figure 2(a), we saw a similar performance that of the needle-in-the -aanii--aaysttckk in the single- state experiment Figure I(a). When we changed the MDP structure to allow for multiple possible paths that led to the special state with the hidden reward, as evident in Figure 2(b), DAVI with all settings of m all reached the asymptote faster than Asynchronous VI and VI. As expected, DAVI converged faster than Asynchronous VI the case of multiple near-optimal policies.
root state value averaged over 200 runs
(a) Tree
averagad over 200 runs
Random MDP
0.125-
0.15
0 VI
state D vallee wew.lvvvveeee
Asynchronous VI
Asynchronous VI
DAVI m =1
DAVI m=1
DAVI m =10
DAVI m =10
DAVI m = =100
0
0
100
02 7
50
run-time in #operations 10
run-time in #operations 10?
nedle-in-the-hayttee experiment: (a) MDP with tree structure (h) random MDP. We run each instance 200 times with a new MDP generated each time. In each run, all algorithms are initialized O.
Figure 2: Multi-state-
We note that perhaps many other real-world problems resemble setting like random-MDP more than needle-in-the-hayseee and hence the result on random-MDP may be more important. See Appendix C for additions experiments with rewards drawn from Normal and Pareto distributions.
7 Conclusion
The advantage of rumning asynchronous algorithms on domains with large state and action space have been made apparent in our studies. Asynchronous VI helps address the large state space problem by making in- in-place updates, but it is still intractable in domains with large action space. DAVI is asynchronous the state updates as in Asynchronous VI, but also asynchronous the maximization over the actions. We show DAVI converges to the optimal value function with probability 1 and also achieves computational complexity closely matching that of VI. We give empirical evidence for DAVI's computational efficiency in several experiments with multiple reward settings.
at a nea--geometric rate with a probability of at least 1 - 8. Asynchronous
Note that DAVI does not address the summation over the states: EvEs p(s'|s, a).())s" in the com- putation of the look-ahead values. the state space is large, computing such sum can also be prohibitively expensive. Prior works by Van Seijen and Sutton (2013) use "small back-ups" to address this problem. Instead summation of all successor states, they update each state's value with respect to one successor state in each update. Another possibility is to sample subset of successor states compute the look-ahead values at the cost of additional failure probability. Combining these techniques with DAVI is potential direction for future work.
Acknowledgments and Disclosure of Funding
We thank Tadashi Kozuno, Csaba Szepesvári, and Roshan Shariff for their valuable comments and feedback. The authors gratefully acknowledge funding from DeepMind, Amii, NSERC, and CIFAR.

---

References
Ahmad, Z., Lelis, L., and Bowling, M. (2020). Marginal utility for planning in continuous or large discrete action spaces. In Advances Neural Information Processing Systems.
Bensoussan, A. (2011). Dynamic Programming and Inventory Control, volume IOS Press.
Bertsekas, D. P. and Tsitsiklis, J. N. (1996). Neuro-Dynamic Programming. Athena Scientific.
Chen, Y. and Wang, M. (2017). Lower bound on the computational complexity of discounted Markov decision problems. arXiv preprint
Danihelka, I., Guez, A., Schrittieserr J., and Silver, D. (2022). Policy improvement by planning with Gumbel. In Proceedings of the International Conference on Learning Representations.
Hubert, T., Schrittweeser J., Antonoglou, I., Barekatain, M., Schmitt, S., and Silver, D. (2021). Learning and planning in complex action spaces. In Proceedings of the International Conference on Machine Learning.
Kearns, M., Mansour, Y., and Ng. A. Y. (2002). A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine learning, 49(2):193-2080
Levorato, M., Narang, S., Mitra, U., and Ortega, A. (2012). Reduced dimension policy iteration for wireless network control via multiscale analysis. In 2012 IEEE Global Communications Conference (GLOBECOM).
Littman, M. L.., Dean, T. L.., and Kaelbling, L. (1995). On the complexity of solving Markov decision problems. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence.
Liu, L., Chattopadhyay, A., and Mitra, U. (2017). On exploiting spectral properties for solving MDP with large state space. In 55th Anmual Allerton Conference on Communication, Control, and Computing.
Liu, L., Chattopadhyay, A., and Mitra, U. (2019). On solving MDPs with large state space: Ex- ploitation of policy structures and spectral properties. IEEE Transactions on Communications, 6151-41551
Powell, W. B., Shapiro, J. A., and Simão, H. P. (2002). An adaptive dynamic programming algorithm for the heterogeneous resource allocation problem. Transportation Science, 36(2):231-249.
Puterman, M. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc.
Szepesvári, C. (2010). Algorithms for Reinforcement Learning. Morgan & Claypool Publishers.
Szepesvári, C. and Littman, M. L. (1996). Generalized Markov decision processes: Dynamic- programming and reinforcement-learning algorithms. Technical report, CS-96-11, Brown Univer- sity, Providence, RI.
Van Seijen, H. and Sutton, R. (2013). Planning by prioritized sweeping with small backups. In Proceedings of the International Conference Machine Learning.
Williams, R. J. and Baird III, L. C. (1993). Analysis of some incremental variants of policy iteration: First steps toward understanding actor-critic learning systems. Technical report, NU-CCS-93-11, Northeastern University, College of Computer Science, Boston, MA.
Zeng, Y. Feng, F., and Yin, W. (2020). AsyncQVI: Asynchronous-paralle Q-value iteration for discounted Markov decision processes with near-optimal sample complexity. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics.
10

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to YYss] [No], or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes]
Did you include the license the code and datasets? [No] proprietary.
The code and the data
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]


Reviews:
[{"review_id": "SRkkW4W4f8j", "reviewer": "Reviewer_592T", "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.", "questions": "I don't have any questions", "limitations": "I have not seen any limitations. This paper is mathematically sound with good intuition.", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. This paper studies one of the most widely studies dynamic programming algorithm: Value iteration (VI). \n2. The proposed DAVI generalizes the idea of asynchrony from states to states and actions.\n3. The computational complexity bound for DAVI nearly match a previously established bound for VI and the convergence rate is nearly geometric rate.\n4. DAVIS could converge to the optimal value function despite only maximizing over a subset of actions in each update.\n\nWeakness:\nI don't work in this field.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Jj-kdlPd9gl", "reviewer": "Reviewer_baze", "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.\n", "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? \n", "limitations": "Limited empirical performance gain.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\nThe paper is well written and the theoretical foundation is solid. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GjYyiPbIJCZ", "reviewer": "Reviewer_qTcp", "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.", "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.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\n\nOne 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.\n\nA 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.\n\nOverall, I think this is a solid paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept