Using Linear Programming for Bayesian Exploration in Markov Decision Processes

1 Introduction

A key problem in reinforcement learning is posed by the need to explore the environment sufficiently in order to discover the sources of reward, while at the same time exploiting the knowledge that the agent has already, by taking actions that yield high return. The most popular techniques in the current literature (e.g.,ϵ-greedy or Boltzmann exploration) are not aimed at efficient exploration; instead, they ensure that action choices are randomized, which enables the agent to try out all actions in all states. This approach guarantees the convergence of reinforcement learning algorithms, but is not efficient from the point of view of the number of samples gathered, and may cause the agent to repeatedly try harmful actions. An extensive line of research has been devoted to directed exploration methods, most of which are based on heuristics that help the agent get data while trying to protect it from "danger", e.g. [Thrun, 1992; Meuleau and Bourgine, 1999]. Recently, several algorithms have been proposed which carry guarantees in terms of the number of samples necessary for the agent to attain almost optimal performance [Kearns and Singh, 1998; Brafman and Tennenholtz, 2001; Strehl and Littman, 2005; Strehl et al., 2006].

In this paper we explore a Bayesian approach to exploration. The initial idea was due to Bellman [1959] who suggested keeping information about the agent's current state of knowledge, in addition to the model being learned by the agent. This method is Bayes-optimal from the point of view of decision making, but its complexity grows exponentially with the horizon considered. This makes it inapplicable except for the case of bandit problems, where it gives rise to Gittins indices. Recently, a body of work on Bayesian reinforcement learning has developed method for approximating the Bayes-optimal procedure for the case of general MDPs [Dearden et al., 1999; Duff, 2002; Wang et al., 2005]. In this paper, we pursue a similar idea, but with two important differences. First, we propose to use linear programming in order to approximate the value function during this procedure. Second, we use a sampling approximation based on the value function to expand the horizon of the decision making process.

The paper is organized as follows. In Section 2 we present the necessary background. In Section 3 we present the linear programming approach to this problem. In Section 4 we present empirical results in three domains.

2 Background

A finite Markov Decision Process (MDP) is a tuple 〈S, A, T , R〉, where S is the finite state space, A is the finite action space, T : S×A×S →ℜ defines the transition probabilities, and R : S×A → ℜ is the reward function, bounded by RMAX. If the agent is in state s ∈ S and performs action a ∈ A, T (s, a, ·) is the distribution over next possible states and R(s, a) is the expected immediate reward. A deterministic stationary policy π : S → A is a function that determines what action to take depending on the current state. One of the goals of reinforcement learning is to find the policy that maximizes the expected discounted return received, given by ∑∞t=1 γ t-1 rt, where rt is the reward received at time step t and γ ∈ (0, 1) is a discount factor. The value of a state V π (s) is given by the expected discounted return received when executing policy π starting from state s:

Note that the upper bound on the value of any policy from any state is RMAX/(1 - γ)

2.1 Hyperstate MDPs

In this paper we consider MDPs in which the transition probabilities T and rewards R are unknown. In this situation, the agent maintains an estimate of the MDP model based on prior knowledge and its observations. For the transition probabilities, it is convenient to use a distribution that is closed under updates performed after observing a state transition. For MDPs with finite state and action sets, the estimate of the transition probabilities can be maintained in a matrix P of size |S| × |A| × |S|. As shown in [Martin, 1967], the Matrix Beta distribution is closed under updates and is a natural choice of distribution for this case. We denote by M = [maij ] the current indexing parameters of the distribution, where maij is simply the number of observed transitions from state i to state j under action a. The expected transition probabilities based on this model are given by E [paij ] = ¯ paij = maij / ∑|S| k=1 maik . Letting the matrix N = [nkij ] denote an additional number of observed transitions from state i to state j under action a, in [Martin, 1967] it is shown that the posterior distribution P ′ with parameters M′ = M+ N is also a Matrix Beta distribution. In what follows, we will denote by Da ij (M) the new distribution obtained from M, through this operation, after observing on transition from state i to state j under action a.

The estimated reward received when performing action a from state i can then be estimated by ¯ ra i = ∑|S| j=1 ¯ paij ˜ ra ij , where ˜ ra ij is the average reward obtained when going for state i to state j under action a. These rewards can be summarized in a matrix ¯R.

The Matrix Beta distribution can be viewed as a summary of the information that the agent has accumulated so far. This information, together with the original MDP states and actions, will form a new, Hyperstate-MDP (HMDP). The actions in the HMDP are the same as in the original MDP. The states of the HMDP consist of pairings of states from S with possible information states M. A hyperstate (i,M, ¯R) contains an MDP state i, all the counts summarizing the agent's experience so far M, and all the estimates of the expected rewards ¯R. The counts define a distribution over all MDP models consistent with the data observed so far.

At any given time step when action a is taken in the original MDP from state i, precisely one transition is observed, to some state j. So, from any given hyperstate (i,M, ¯R), we can consider taking all possible actions a ∈ A. If such an action results in a state j, the new hyperstate will be (j, Da ij (M), Da ij ( ¯R)), where we have updated the innformation model as described above to reflect the new transition. We note that this update only affects the parameters for state i; all parameters for other states do not change. Assuming that there are a fixed number of rewards R that can be observed, each hyperstate in the HMDP has at most |A|×|S|×R successors. Moreover, each successor hyperstate is uniquely indexed. Hence, the HMDP is an infinite tree. Note also that the HMDP takes into account all possible transitions. Hence, it is fully known, even though the MDP itself is not.

One can express the Bellman optimality equations for an HMDP as:

Solving this set of equations exactly would yield an optimal policy [Bellman and Kalaba, 1959; Martin, 1967]. However, it is clear that the number of states in the HMDP is infinite, so an exact solution is intractable. It is also clear that the number of hyperstates increases exponentially with the depth of the tree, so an exact solution of a finite-horizon subset of the tree would be limited to very shallow depths. The focus of this paper is to present an algorithm for computing an empirically good learning policy from a finite subset of the tree. Theoretical guarantees will be left for future work and we will focus on comparing the performance of our algorithm to other well-known exploration techniques.

2.2 RelatedWork

Optimal learning has seen an increase in interest in recent years. Much of the recent work has been spurred by [Kearns and Singh, 1998], where the authors introduce E3 , an algorithm that is guaranteed to converge to an optimal learning policy in polynomial time. The drawbacks with this algorithm are its difficulty of implementation, and the intuition that it does not necessarily scale well to large state spaces. A practical model-based algorithm with similar guarantees was given in [Brafman and Tennenholtz, 2001]. More advanced model-based algorithms with PAC guarantees, based on realtime dynamic programming, have been recently proposed in [Strehl and Littman, 2005; Strehl et al., 2006]. These methods explore by assigning a reward for exploratory actions. The drawback of both [Kearns and Singh, 1998] and [Strehl et al., 2006] is that their strategies are myopic - they do not consider the long term effects their actions may have on the total reward.

Using hyperstates as the model for exploration overcomes this myopic behavior. The concept of hyperstates was first introduced in [Bellman and Kalaba, 1959], which refers to this model as an adaptive control process. Although mathematically rich, the paper presents no algorithmic approach for this idea. In [Duff, 2002], various heuristic methods are presented for approximating an exact solution to the adaptive control process. These produce empirically good results, but with no general theoretical guarantees.

Wang et al [2005] propose sampling from the infinite hypertree to produce a small, more manageable tree. They solve exactly the MDPs along the path they are sampling, which gives them estimates for the values of different actions. Then, they use Thompson sampling to expand the tree locally under promising actions. The authors estimate unsampled regions by effectively 'copying' the last sampled node down to the current planning horizon. Finally, sparse sampling [Kearns et al., 1999] is used to decide what action is optimal. A correction procedure is used when the desired horizon has not been reached. Empirical results demonstrate that the algorithm performs well in comparison to other algorithms. Furthermore, the sparse sampling technique enables the algorithm to be able to handle infinite state and action spaces.

3 Solving the hyperstate MDP

In this paper we take an approach similar to [Wang et al., 2005] but with two key differences. First, action-value estimates are maintained for the state-action pairs of the original MDP, in addition to hyperstate values. The action-values are updated from the obtained samples using standard Qlearning [Sutton and Barto, 1998]. Hence, we always have an easy estimate of how good different actions are. Second, we compute the value of the hyperstates using Linear Programming. Linear Programming (LP) is a technique that has been around for a long time, is well understood and has an elegant theory [Puterman, 1994]. Furthermore, recent work in approximate linear programming [de Farias and Roy, 2003; 2004; Hauskrecht and Kveton, 2004]) suggests that this approach can be used to work with continuous states using linear function approximation. We are hopeful that such techniques could eventually be used to generalize our approach to continuous MDPs. However, for now we limit ourselves to discrete MDPs.

In a manner similar to [Schweitzer and Seidmann, 1985], the optimality equations for the hyperstate MDP can be formulated as a linear program as follows:

such that

for all states i ∈ S, all actions a ∈ A and all information states M. We will refer to this formulation as the exact LP. However, at a depth d, the number of hyperstates is at least O ((|S| × |A|)d ) (more if we consider several possible reward levels). This means that for depth d the linear program has at least O ((|S| × |A|)d ) variables and constraints, a prohibitive amount.

In [Kearns et al., 1999] the authors overcome a similar obstacle by constructing a sparse sample tree. We apply a similar idea here and construct a sampling tree incrementally. More precisely, we sample from the hyperstate MDP using our current estimates of the action values to decide what to do. At each node, we use the corresponding estimate of the dynamics of the system to sample the next node in the trajectory. Each trajectory is completed to a desired horizon. We continue constructing trajectories in this way until a maximum desired number of samples has been reached.

If we encounter a hyperstate for which a value was computed already using an LP, we use the LP-based estimate (which, in the limit, approaches the true optimal value of the correspondingMDP state). If such a value has not been computed, the action-value function for the MDP state is used instead. Note that any unsampled regions constitute a subtree of our hyperstate MDP. These unsampled subtrees are estimated by setting the value of the hyperstate at the root of the subtree, (i,M,R) to the value of the correspondinng MDP state i. With this method, we can effectively choose how many variables and constraints we want to use in the linear program.

Once the sampled hyper tree is built, we can solve it using linear programming. Then, in order to gather more samples, we will choose action greedily based on the values computed by the linear program. If we enter an unsampled region, the action choice becomes greedy with respect to the value estimates attached to the original MDP states, until we decide to construct a new hyper tree and compute new values.

Algorithm 1 Explore(levels, maxSamples, numSteps, maxEpochs)

• 1: Initialize the matrix of counts to all 1s (uniformdistribution)
• 2: while epochs ≤ maxEpochs do
• 3: Construct a hyper-tree of a depth of levels using maxSamples sampled trajectories
• 4: Solve the LP of the sample hypertree
• 5: Choose action greedily based on hyperstate values
• 6: Observe transition and update hyper parameter for observed transition
• 7: for i = 1 to numSteps do
• 8: Choose action greedily based either on current hyperstate value or current estimate of state values
• 9: Observe transition and update hyper parameters based on the observed transition
• 10: end for
• 11: epochs ← epochs+numSteps1
• 12: end while

Algorithm 1 presents an outline for our approach. The maxEpochs parameter defines how many total samples will be gathered from the environment. The levels parameter describes the depth to which we will expand the sampled hypertree. The maxSamples parameter controls how many trajectories are sampled (i.e., the width of the tree). Together, these two parameters control how large each linear program is. The numSteps parameter defines how many steps in the environment are taken before the LP solution is recomputed. This allows us to trade off the precision of the computation against time. Obviously, if we re-compute the LP after every sample, we always generate samples based on the action that is truly believed to be best. If we wait longer, we may start selecting actions based on imperfect estimates of the values of the underlyingMDP. However, this speeds up the computation significantly.

4 Empirical results

We tested our algorithm on three different problems. For all domains, results are averaged over 30 independent runs. We compared our approach with a Q-learning agent (with α = 0.1) using an ϵ-greedy approach (with varying values of ϵ), and with the algorithm described in [Wang et al., 2005]. We also experimented with a myopic agent (acting only based on immediate reward), and against an agent which chooses actions randomly. These last two algorithms did far worse than all the others, and so are omitted here for clarity. For our algorithm, we experimented with different parameter settings, as explained in more detail below. Because the primal LP has more constraints than variables, the dual was solved instead.

We also considered two different possible uses of the model that is constructed by our algorithm. In the first version, once the desired number of epochs has been completed, we perform dynamic programming using the acquired model, to determine a value function for the original MDP. In the second setting, We just use the values determined by the LP as value estimates. Obviously, this latter approach is faster, since no extra computation is required, but it is also more imprecise.

Small MDP

The first problem was a two-state, three-action MDP, described in the left panel of Figure 3. Intuitively, the best policy is to perform action 1 until state 2 is reached, then do action 3 and keep in the same state.

The center graph compares our algorithm, with parameters levels = 7,numSteps = 6,maxSamples = 35, with Qlearning using three different values of ϵ (0.01, 0.1 and 0.5) and the approach by Wang et al. For all algorithms we plot average return per episode. Note that the implementation of the algorithm described in [Wang et al., 2005] was not able to handle more than 35 samples, which is why we performed the comparison at this level. Although Q-Learning with ϵ = 0.1 outperformed all the other algorithms in this graph, we can see that if we allow our algorithm 50 samples to construct the hypertree, it performs better than the rest. Interestingly, in this case, using the values from the LP also gives better performance than doing one last step of dynamic programming.

Bandit problem

The second problem is similar to a bandit problem with two slot machines (bandits) and three actions. This problem was modeled using three states and three actions, with dynamics as given in figure 4. The dynamics are shown in the left panel for action 1 (solid), action 2 (dashed) and action 3 (solid grey). The leftmost state corresponds to not winning, the middle state corresponds to winning under machine 1 and the rightmost state corresponds to winning under machine 2. There is no cost associated with gambling.

For the comparison between algorithms, we use parameters levels = 6,numSteps = 5,maxSamples = 45. For this problem [Wang et al., 2005]'s algorithm was able to handle up to 45 samples as well. Our algorithm outperformed all the others. In Figure 4 we can see that even with only 15 samples, our algorithm does almost as well as the best Qlearning algorithm.

Grid World

The third problem is a 2x4 gridWorld with a reward of +1 in the top right state and 0 everywhere else. There are four actions (north, south, west and east) with a 0.1 probability of remaining in the same state. If the agent tries to move into a wall it will deterministically stay in the same state. The parameter values used are levels = 9,numSteps = 8,maxSamples = 15.

This is a larger problem than the first two, and all the other algorithms are 'stuck' with low reward, while our algorithm is able to find a good policy. In figure ?? it is clear that using Dynamic Programming to obtain state value estimates is advantageous for this task.

It is interesting to see that in the first two problems using the values returned by the LP to estimate the state values yields better returns initially. This is probably because of the 'lookahead' nature of HMDP. However, for the gridWorld problem the performance is much better when using the DP solution to estimate the state values. This behavior is most probably due to the size of the hypertree created. As the state and action space get bigger, more samples are needed to obtain state value estimates that are closer to the true values. It should be noted that even when the DP was not solved exactly, in all cases the performance when using HMDPs was superior to the other algorithms. We note that we also experimented with Boltzmann exploration algorithms (omitted from the plots for clarity), but in all cases their performance was similar to the Q-learning algorithms.

Running time

The results demonstrate that our approach has an advantage compared to the other methods in terms of accuracy. However, in terms of computation time, using hyperstates is obviously much slower than Q-learning. Table 1 plots the average running time per episode when solving the DP to estimate the state values versus using the values returned by the LP for the different domains, as well as the running time of [Wang et al., 2005]'s algorithm. It is worth observing the difference in performance/running time depending on how the state values are estimated (solving with DP or using the values returned by the LP). Although our algorithm is considerably slower when solving with DP, it is faster than [Wang et al., 2005]'s algorithm when using the values returned by the LP solution. However, for the gridWorld problem, although solving with HMDP is slower than [Wang et al., 2005]'s algorithm, the savings when using [Wang et al., 2005]'s algorithm are insignificant when compared against the superior performance demonstrated in figure 3.

5 Conclusions and future work

The aim of this paper was to demonstrate the performance of Bayesian learning using sparse sampling and linear programming. It was observed that in general using hyperstates does lead to greater average returns when exploring an unknown environment than if we used simpler exploration techniques or even state-of-the-art techniques such as the algorithm presented in [Wang et al., 2005]. The drawback of this technique is that it may leave certain areas of the environment unexplored, but this could be the desired behavior. If you consider a physical agent (such as a robot) placed with the task of exploring a new environment, you would want the agent to avoid areas which could cause harm to its mechanical parts or even to other people around it, yet still explore sufficiently to try to reach states with high reward. A situation like that would justify the increase in computation. Furthermore, the method of sparse sampling could allow the hypertree to have a greater depth, and thus, the agent could see states that other myopic methods may not be able to. This ability to value actions not only on their immediate but long-term effect makes Bayesian learning a good candidate for exploratory agents.

The next step is to obtain theoretical guarantees for our algorithm. We would also like to implement the algorithms presented in [Strehl et al., 2006] and possibly [Duff, 2002] to empirically compare our algorithm against more of the latest advances in Bayesian decision theory. It would also be interesting to try our algorithm against problems with continuous state and/or action spaces. Placing a Gaussian over sampled points could assist us in approximating the full hypertree better. Further work could be to apply approximation techniques to the full hyper-tree, in a manner similar to what was done in [de Farias and Roy, 2003] and [Hauskrecht and Kveton, 2004] for MDPs with very large state spaces.

5.1 Acknowledgments

This work was supported in part by NSERC and FQRNT.