Bayesian Real-Time Dynamic Programming

1 Introduction

Markov Decision Processes (MDPs) [Puterman, 1994] provide a convenient framework for modeling fully-observable stochastic planning problems. In an MDP, the agent computes a policy - a mapping from states to actions - in order to maximize a stream of rewards. A popular approach to policy computation is through a value function - a function that assigns a value to each world state. The computation of the value function can be either synchronous, where all states are updated during each iteration, or asynchronous, where the agent updates some states more than others.

Recent years have seen a resurgence of interest in asynchronous dynamic programming solutions to MDPs [Bertsekas, 1982]. Of particular interest has been the trial-based real-time dynamic programming (RTDP) approach [Barto et al., 1993] as evidenced by a variety of recent work [Bonet and Geffner, 2003a; 2003b; McMahan et al., 2005; Smith and Simmons, 2006]. RTDP algorithms have a number of distinct advantages for practical MDP solutions, specifically:

1. Anytime performance: RTDP algorithms can be interrupted at any time, generally yielding a better solution the longer they are allowed to run.
2. Optimality without exhaustive exploration: By focusing trial-based search on states reachable from the set of initial states, RTDP algorithms may obtain an optimal policy while visiting only a fraction of the state space.

Recent state-of-the-art advances in RTDP algorithms such as bounded RTDP (BRTDP) [McMahan et al., 2005] and focused RTDP (FRTDP) [Smith and Simmons, 2006] propose (a) maintaining upper and lower bounds on the value function; (b) using the policy derived from the lower bound to provide guarantees on policy performance; and (c) directing exploration (and termination) by the uncertainty of a state's value, as measured by the gap between its upper and lower value bounds. As BRTDP and FRTDP both prioritize search according to value uncertainty, they may execute needless updates in areas of the state space where the policy has converged, but the values have not.

To address this deficiency, we take a Bayesian perspective on the upper and lower bounds in order to express a belief distribution over value functions. We then use this distribution in a myopic value of perfect information (VPI) [Howard, 1966] framework to approximate the expected improvement in decision quality resulting from the update of a state's value. This leads us to the development of a novel algorithm called VPI-RTDP that directs exploration (and termination) according to this VPI analysis. Empirically, VPI-RTDP results in an improvement over state-of-the-art RTDP methods, yielding up to a three-fold reduction in the amount of time and unique states visited to achieve comparable policy performance.

2 Background

2.1 Markov Decision Processes

A Markov decision process (MDP) is a tuple 〈S,A, T,R, γ〉 [Puterman, 1994]. S = {s1, . . . , sn} is a finite set of fully observable states. A = {a1, . . . , am} is a finite set of actions. T : S × A × S → [0, 1] is a known stationary, Markovian transition function. R : S × A → R is a fixed known reward function associated with every state and action. γ is a discount factor s.t. 0 ≤ γ ≤ 1 where rewards k time steps in the future are discounted by γ k . There is a set of initial states I ⊆ S, and a possibly empty set of absorbing goal states G ⊂ S where all actions lead to a zero-reward self-transition with probability 1.

Algorithm1: RTDP

begin

// Initialize ˆ Vh with admissible value function ˆ Vh := Vh while convergence not detected and not out of time do depth := 0 visited.CLEAR() // Clear visited states stack Draw s from I at random // Pick initial state while (s /∈ G) ∧ (s ̸= null ) ∧ (depth < max-depth) do depth := depth + 1 visited .PUSH(s) ˆ Vh(s) := UPDATE( ˆ Vh, s) // See (2) & (3) a := GREEDYACTION( ˆ Vh, s) // See (4) s := CHOOSENEXTSTATE(s,a) // See (5) // The following end-of-trial update is an optimization // not appearing in the original RTDP while ¬visited.EMPTY() do s := visited.POP() ˆ Vh(s) := UPDATE( ˆ Vh, s) return ˆ Vh end

A policy π : S → A specifies the action a = π(s) to take in state s. Our goal is to find a policy that maximizes the value function, defined as the sum of expected discounted rewards

where rk is the reward obtained at time step k.

2.2 Synchronous Dynamic Programming (DP)

Value iteration (VI) is a synchronous dynamic programming (DP) solution to an MDP. Starting with an arbitrary V 0 (s), VI performs value updates for all states s, computing the next value function V k (s) := UPDATE(V k-1 , s):

This update is known as a Bellman update.

The greedy policy π(s) = GREEDYACTION(V k , s) w.r.t. V k and state s is defined as follows:

After some finite number of iterations k of VI, the greedy policy with respect to V k is provably optimal [Puterman, 1994].

2.3 Asynchronous DP and Real-time DP

Asynchronous DP methods [Bertsekas, 1982] are a variant of dynamic programming that apply the Bellman update to

Algorithm 2: CHOOSENEXTSTATE-BRTDP(s, a)

begin

// Compute bound gap of reachable states s′ , use to select ∀s′ , b(s′ ) := T(s, a, s′ )( ˆ Vh(s′ ) - ˆ Vl(s′ )) B := Ps′ b(s′ ) if B < ˆ Vh(s)- ˆ Vl (s) τ then return null return s′ ∼ b(·) B end

states in an arbitrary order while still retaining convergence properties under certain conditions. The real-time dynamic programming (RTDP) [Barto et al., 1993] algorithm (Algorithm 1) is an asynchronous DP approach that updates states encountered during trial-based MDP simulations. RTDP explores the state space in depth-limited trials and performs Bellman updates at each visited state. RTDP visits states s′ sampled from the transition distribution (s′ ∼ T (s, a, ·)) for the current greedy action a and current state s, i.e.,

We say that Vh is an admissible upper bound over the optimal value function V ∗ if Vh(s) ≥ V ∗ (s) for every state s. Similarly, Vl is an admissible lower bound if Vh(s) ≤ V ∗ (s). Given an admissible upper bound, RTDP converges to the optimal value function in the limit of trials [Barto et al., 1993].

One key advantage of RTDP is that it may only need to explore a small subset of states to obtain an optimal policy π∗ w.r.t. I if the subset of states reachable from I under π∗ (the relevant states for π∗ ) is small.

2.4 RTDP Extensions

One drawback of RTDP is that its random exploration of states in (5) may focus search in areas of the state space that already have converged values. Since this wastes computation, one improvement is to focus exploration on states with high value uncertainty and terminate when there is low uncertainty. This is the motivation behind the bounded RTDP (BRTDP) [McMahan et al., 2005] and focused RTDP (FRTDP) [Smith and Simmons, 2006] extensions to RTDP.

BRTDP and FRTDP both maintain upper and lower bounds on the value function. Assuming that the upper and lower bounds are admissible, subsequent DP updates preserve admissibility [McMahan et al., 2005].

In BRTDP and FRTDP, we update both bounds using ˆ Vh(s) := UPDATE( ˆ Vh, s) and ˆ Vl(s) := UPDATE( ˆ Vl, s). In BRTDP, the CHOOSENEXTSTATE routine that directs exploration is modified (Algorithm 2), prioritizing states by the gap between their upper and lower value bounds. Trials terminate when the sum of these gaps is below a threshold. FRTDP provides a similarly motivated uncertainty-based state selection and trial termination criteria.

3 Bayesian Real-time Dynamic Programming

While BRTDP and FRTDP often converge faster than RTDP, they can still execute redundant updates in areas of the state space where the policy has already converged, but the values have not. Thus, in place of focusing exploration and updates on states with the highest value uncertainty, what we would really like is to prioritize updates on those states whose value update may lead to the greatest improvement in policy value.

Performing this value of information analysis would be prohibitively expensive if done exactly and non-myopically so we use a myopic Bayesian value of information framework [Howard, 1966] to approximate the expected improvement in decision quality resulting from a state's value update.

We begin by rewriting (2) and (3) using a vector notation where ⃗Γa,s = γT (s, a, ·):

3.1 Bounds and Belief Distributions

In order to take an expectation in a Bayesian framework, we need to assign probabilities to our current value beliefs.

Let ⃗Vl and ⃗Vh represent vectors of lower and upper bounds respectively, and ⃗θ = 〈⃗Vl, ⃗Vh〉. The bounds Vh(s) and Vl(s) for state s may be correlated with the bounds Vh(s′ ) and Vl (s′ ) for any state s′ reachable from s under some policy π. Determining these correlations is tantamount to performing DP backups, which is precisely the operation that we are trying to optimize.

Given that we have no additional immediate knowledge about possible belief values vs ∈ [Vh(s), Vl(s)] for state s, we can only reasonably assume that vs is uniformly distributed between these lower and upper bounds. This assumption is not simply for convenience. Without knowing how values were updated or being able to determine correlations between them, we have no more reason to believe that the true value v∗ s is at the mean [Vh(s) + Vl(s)]/2 rather than at one of the boundaries Vh(s) or Vl(s), or anywhere in between. For model-based DP, the value updates are not sampled in a statistical sense and thus the central limit theorem and associated normality assumptions do not apply.

We use ⃗θ to parameterize a multivariate uniform distribution P (⃗v|⃗θ) for ⃗v ∈ R|S| that is consistent with the upper and lower bounds ⃗ θ. P (⃗v|⃗θ) can be conveniently factorized as

where δVl(s)(vs) is a Dirac delta function.

3.2 TheMyopic Value of Exploration

With a value belief distribution that is the uniform hyperrectangle between upper and lower value bounds, we can now write out the integral for the expected value of Q(a, s) under the current beliefs and evaluate it in closed-form:

We now use this to determine the states t ∈ S for which the expected information gain of updating value V (t) is greatest. Let us assume that we are only interested in the impact of the value vt on the current policy value. Given that we do not know the true value v∗ t , we can use a value of perfect information (VPI) analysis [Howard, 1966] where we assume that a clairvoyant source informs of the true value v∗ t = V ∗ (t).

Using this assumption of perfect external knowledge about v∗ t to refine our beliefs, we replace the previous upper and lower bounds for state t in P (v|⃗θ) with v∗ t :

Integrating the above, rearranging terms, and substituting (8) yields a simplified form of this expectation:

Now, whereas (8) evaluated to a constant since all values in ⃗Vh and ⃗Vl are known, (9) evaluates to the function c(a,s,t,⃗ θ) + d(a,s,t)v∗ t linear in v∗ t since all values other than v∗ t are constants.

To evaluate the gain of knowing v∗ t , we take the analytical framework of [Dearden et al., 1998] used for analyzing the value of action selection in the model-free MDP setting and adapt it for analyzing the value of state exploration in the model-based framework. Let a∗ = GREEDYACTION(⃗Vh, s) (since convergence of RTDP requires exploring states reachable from the best upper bound action). We could evaluate the gain in Q-value for state s by using a rather than a∗ if we knew the exact value of successor state t is v∗ t :

Gain s,t,a,a∗ (v∗ t ) is only non-zero when knowledge of v∗ t indicates that a∗ is better than a in s and the gain is then the difference in utility. We note that Gains,t,a,a∗ (v∗ t ) must always be non-negative because more information can never reduce policy quality.

In reality, we do not know v∗ t . However, we can still write out the expected myopic VPI of being in state s with current best policy a∗ and knowing the value of t is v∗ t by integrating over it w.r.t. our beliefs P (v∗ t |⃗θ):

Since we are looking at the gain over multiple actions and only one of them can be optimal, we take the maximum expected gain possible. VPI s,a∗ (t) provides us with an approximate estimate of the myopic VPI of the impact that an update of state t's value will have on the policy quality at s.

VPI s,a∗ (t) might seem difficult to evaluate. But in Figure 1 we show that the calculation intuitively only requires a maximization over the expected gains of taking each a ̸= a∗ instead of a∗ . This can be computed efficiently with the same O(|S| · |A|) computational complexity as the Bellman backup at a single state - for every next state t, VPI s,a∗ (t) is the maximizing Gains,t,a,a∗ (v∗ t ) over all actions a ̸= a∗ , which is a constant time calculation consisting of (a) computing the line equations (9) for a and a∗ used by Gains,t,a,a∗ (v∗ t ), (b) determining the intersection point of these two lines and (c) calculating the triangular area between the lines and value bounds where a dominates. As the Bellman backup must already be computed four times at each state visited during a trial, this does not change the complexity of the algorithm.

3.3 VPI Exploration Heuristic

We use the VPI s,a∗ (t) calculation to prioritize state exploration and trial termination in Algorithm 3. Using dual bound updates and Algorithm 3 in place of CHOOSENEXTSTATE(s, a) in RTDP (Algorithm 3) yields the VPI-RTDP algorithm. This approach has roughly the same structure as BRTDP and FRTDP except that VPI s,a∗ (t) is used in conjunction with bound gap Vh(s) -Vl(s) heuristics.

The VPI s,a∗ (t) calculation is uninformative when bounds are close to their maximal uncertainty. We thus revert to the BRTDP heuristic in this case; in practice we use a threshold β that is 95% of the maximum possible bound. With probability α we avoid termination when VPI s,a∗ (t) is zero for all states t since this is a local termination heuristic that ignores the need of predecessor states to reduce uncertainty.

VPI-RTDP has the same theoretical guarantees as BRTDP [McMahan et al., 2005] when α > 0 quite trivially since all states with non-zero probability of an update by BRTDP must then also have a non-zero probability of update under VPI-RTDP. However, this is mainly of theoretical concern since we have found it advantageous to use very small α in practice, e.g., α = 0.001 as used in our experiments.

Algorithm 3: CHOOSENEXTSTATE-VPI(s, a)

begin // Check for large bound gap ∀t, b(t) := T(s, a, t)( ˆ Vh(t) - ˆ Vl(t)) B := Pt b(t) if maxt b(t) > β then return t ∼ b(·) B // If VPI non-zero, focus on value of information ∀t, v(t) := VPI s,a(t) V := Pt v(t) if V > 0 then return t ∼ v(·) V // VPI is zero, continue with probability α r ∼ Uniform(0,1) if r < α ∧ B ̸= 0 then return t ∼ b(·) B return null

end

4 Empirical Results

We evaluated RTDP, BRTDP (τ = 10), FRTDP (ϵ = .001) and VPI-RTDP on the racetrack benchmark domain [Barto et al., 1993]. Example racetrack topologies that we use are provided in Figure 2. We borrow some topologies from [Smith and Simmons, 2006] as well as variations of their slippage and wind enhancements to the original racetrack problem.

The state in this problem is a combination of a car's coordinate position 〈x, y〉 and velocity 〈x′ , y′ 〉 in each coordinate direction. A car begins at one of the initial start states (chosen uniformly randomly) with velocity 〈x′ , y′ 〉 = 〈0, 0〉, receives -1 for every action taken, except for 0 in the absorbing goal states. Actions 〈x′′ , y′′ 〉 available to the car are integer accelerations {-1, 0, 1} in each coordinate direction. If the car hits a wall, then its velocity 〈x′ , y′ 〉 is reset to 〈0, 0〉. Nominally, the car accelerates according to the intended action. However, a car may skid with probability .1, thus resulting in 0 acceleration in each direction. Or with probability .8 the wind may perturb the commanded acceleration by a uniform choice of {〈-1, 0〉, 〈0,-1〉, 〈1, 0〉, 〈0, 1〉}. We use discount γ = 1 so this is a stochastic shortest paths (SSP) MDP. We set max-depth = 200 for these problems and thus use -max-depth to initialize the lower bounds. For informed upper bound initialization we used the negative of the Manhattan distance to the closest goal divided by twice the maximum velocity (clearly an optimistic estimate).

In Figure 3, we show the average policy reward for the lower bound greedy policy vs. the execution time (top) and the number of unique states visited (bottom) for each algorithm on four Racetrack problems. 95% confidence intervals are shown on all average reward estimates. VPIRTDP outperforms all competing algorithms on each problem and reaches optimality visiting a smaller fraction of the state space (i.e., number of unique states) than the competing algorithms. On the largest problem (Block-80), VPI-RTDP shows roughly a three-fold reduction in the amount of time and number of unique states visited required to achieve performance comparable to the best competitor (BRTDP). For the Block problems especially, VPI-RTDP managed to avoid visiting the many irrelevant states leading away from the initial state and goal - the VPI of these states was low (so VPI avoided these states) even while their bound gap was still large (BRTDP and FRTDP could not avoid these states).

In Figure 4, we analyze the scaling behavior of each algorithm as a function of problem size. Shown are the time and number of unique states visited required to achieve average policy return of at least -100 vs. the length parameter in the Block problem (results averaged over 120 runs of each algorithm). The number of states in the Block problem grows slightly superlinearly with length as higher velocities can be achieved on longer tracks. We chose -100 as a policy performance comparison point since it is roughly the point of inflection in performance for all algorithms shown in Figure 3

- after -100 is reached, the quality of the policy rapidly improves with future trials. The figure shows that as problem size increases, the time and space performance gap between VPI-RTDP and competing algorithms significantly widens.

5 RelatedWork

Other extensions of RTDP and other efficient algorithms that focus dynamic programming on reachable states were suggested in the past. Labeled RTDP (LRTDP) [Bonet and Geffner, 2003b] improves on basic RTDP by labeling solved states when their values (and the values of their successors) have converged, thus not requiring future updates. Heuristic Dynamic Programming (HDP) [Bonet and Geffner, 2003a]

combines an even stronger version of this labeling approach with a heuristic search algorithm. LAO* and Improved LAO* [Hansen and Zilberstein, 2001] are policy iteration approaches to solving MDPs while limiting themselves to relevant states for the current greedy policy. As BRTDP and FRTDP were shown to outperform LRTDP and HDP [McMahan et al., 2005; Smith and Simmons, 2006] and LRTDP was shown to outperform (Improved) LAO* [Bonet and Geffner, 2003b], we focused our experimental comparison on BRTDP and FRTDP as the current state-of-the-art RTDP algorithms. That BRTDP outperforms LRTDP is not surprising - both avoid visiting converged states (LRTDP labels them), but BRTDP also prioritizes states by their degree of convergence.

Russell and Wefald [1991] proposed the idea of using myopic value of information heuristics for search node expansion. This idea was later applied to MDPs in the form of Bayesian Q-learning [Dearden et al., 1998], which presents a technique to balance exploration and exploitation in a modelfree Q-learning approach. While Bayesian Q-learning inspired this work, there are subtle, but important differences. Bayesian Q-learning is concerned with the expected information gain of action selection and not with the information gain of exploring individual states as required here by the RTDP framework. Furthermore, Bayesian Q-learning models its beliefs using a normal-gamma distribution leading to a VPI integral that cannot be computed in closed-form thus requiring sampling methods for evaluation. Our model-based framework and uniform hyper-rectangle Bayesian belief distribution allows us to derive a closed-form computation for the VPI of the same complexity as the Bellman backup.

The sensitivity analysis used in the hierarchical planner DRIPS [Haddawy et al., 1995] is the closest approximation we have found in the literature of the model-based VPI analysis we derived here. However, in our experiments adapting DRIPS to the RTDP setting (unreported here due to space limitations), VPI outperformed DRIPS.

6 Concluding Remarks

We contributed a novel, efficiently computable, and closedform Bayesian value of information analysis that can be used as a state exploration and trial termination heuristic in a new Bayesian RTDP algorithm: VPI-RTDP. VPI-RTDP attempts to avoid the pitfalls of BRTDP and FRTDP by focusing search on those states with the greatest potential impact on policy quality, not just value uncertainty as done previously. Empirically, VPI-RTDP leads to an improvement over state-of-theart RTDP methods, yielding up to a three-fold reduction in the amount of time and fraction of state space visited to achieve comparable policy performance. Theoretically, VPI-RTDP has the same optimal convergence guarantees as BRTDP.

One potential extension of this work would be to continuous state or action MDPs. Certain special cases such as MDPs with linear Q-functions over the state or action space might admit computationally efficient, closed-form derivation of VPI heuristics.

Acknowledgements

NICTA is funded by the Australian Government's Backing Australia's Ability and ICT Centre of Excellence programs. Kurt Driessens was sponsored by the fund for scientific research (FWO) of Flanders as a postdoctoral fellow.