A Bayesian Approach to Imitation in Reinforcement Learning

1 Introduction

Reinforcement learning is a flexible, yet computationally challenging paradigm. Recent results demonstrating that un­ der certain assumptions the sample complexity of reinforce­ ment learning is polynomial in the number of problem states [Keams and Singh, 1998] are tempered by the sober fact that the number of states is generally exponential in the number of the attributes defining a learning problem. With recent in­ terest in building interacting autonomous agents, reinforce­ ment learning is increasingly applied to multiagent tasks, a development which only adds to the complexity of learning [Littman, 1994; Hu and Wellman, 1998]. In this paper, we ex­ amine multi-agent reinforcement learning under the assump­ tion that other agents in the environment are not merely ar­ bitrary actors, but actors "like me". That is, the other agents may have similar action capabilities and similar objectives. This assumption radically changes the optimal learning strat­ egy. Information about other agents "like me" can give the learning agent additional information about its own capabili­ ties and how these capabilities relate to its own objectives. A number of techniques have been developed to exploit this, in­ cluding imitation [Demiris and Hayes, 1999; Mataric, 2002], learning by watching [Kuniyoshi eta!., 1994], teaching or programming by demonstration [Atkeson and Schaal, 1997] behavioral cloning [Sammut et al., 1992], and inverse rein­ f orcement learning [Ng and Russell, 2000].

Learning by observation of other agents has intuitive ap­ peal; however, explicit communication about action capabil­ ities between agents requires considerable infrastructure: a

Craig Boutilier

University of Toronto Toronto, ON, Canada M5S 3H5 cebly@cs. toronto. edu

communication channel , a sufficiently expressive represen­ tation language, a transformation between possibly different agent bodies, and an incentive to communicate. In dynamic, competitive domains, such as web-based trading, it is unreal­ istic to expect all agents to be designed with compatible rep­ resentations and altruistic intentions. Observation-based tech­ niques, in which the learning agent observes only the outward behaviors of another agent, can reduce the need for explicit communication. Implicit communication through passive ob­ servations has been implemented as implicit imitation [Price and Boutilier, 1999; 200 1]. In this model, the effects of other agents' action choices on the state of the environment can be observed, but the internal state of other agents and their ac­ tion control signals are not observable. Independent explo­ ration on the part of the observer is used to adapt knowledge implicit in observations of other agents to the learning agent's own needs. Unlike classic imitation models, the learner is not required to explicitly duplicate the behavior of other agents.

In this paper, we recast implicit imitation in a Bayesian framework. This new formulation offers several advantages over existing models. First it provides a more principled, and more elegant approach to the smooth pooling of infor­ mation from the agent's prior beliefs, its own experience and the observations of other agents (e.g. , it eliminates the need for certain ad hoc tuning parameters in current imitation mod­ els). Second, it integrates well with state-of-the-art explo­ ration techniques, such as Bayesian exploration. Finally, the Bayesian imitation model can be extended readily to partially­ observable domains, though the derivation and implementa­ tion are considerably more complex and are not reported here.

2 Background

We assume a reinforcement learning (RL) agent is learning to control a Markov decision processes (MDP) (S, A 0 , R 0 , D), with finite state and action sets S , A 0 , reward function Ra : S f---+ R, and dynamics D. The dynamics D refers to a set of transition distributions Pr(s, a, ·). The actions Ao and rewards Ra are subscripted to distinguish them from those of other agents (see below). We assume throughout that the agent knows Ra but not the dynamics D of the MDP (thus we adopt the "automatic programming" perspective), and has the objective of maximizing discounted reward over an infi­ nite horizon. Any of a number ofRL techniques can be used to learn an optimal policy 1r : S f---+ A 0 · We focus here on modelbased RL methods, in which the observer maintains an esti­ mated MOP (S, A0 , R0 )J), based on the set of experiences (s, a, r, t) obtained so far. At each stage (or at suitable inter­ vals) this MOP can be solved exactly, or approximately using techniques such as prioritized sweeping [Moore and Atkeson, 1993]. Since Ro is known, we focus on learning dynamics.

Bayesian methods in model-based RL allow agents to in­ corporate priors and explore optimally. In general, we em­ ploy a prior density P over possible dynamics D , and update it with each data point (s, a, t). Letting H 0 = (so, s1 , .. . , sr) denote the (current) state history of the observer, and A 0 = ( ao , a 1, . . . , ar _1) be the action history, we use the poste­ rior P(DJH0 , Ao) to update the action Q-values, which are used in tum to select actions. The formulation of Dearden et a!. 1999 renders this update tractable by assuming a con­ venient prior: P is the product of local independent densi­ ties for each transition distribution Pr( s, a,·); and each den­ sity P(Ds,a) is a Dirichlet with parameters n s,a . To model P(D 8 ·a ) we require one parameter ns,a,s' for each possible successor state s'. Update of a Dirichlet is straightforward: given prior P(D 8 ·a; n s,a) and data vector cs ,a (where c:·a is the number of observed transitions from s tot under a), the posterior is given by parameters ns,a + cs,a . Thus the poste­ rior in Eq. 1 can be factored into posteriors over local families:

where Hg·a is the subset of history composed of transitions from state s due to action a, and the updates themselves are simple Dirichlet parameter updates.

The Bayesian approach has several advantages over other approaches to model-based RL. First, it allows the natural in­ corporation of priors over transition and reward parameters. Second, approximations to optimal Bayesian exploration can take advantage of this approach, and the specific structural as­ sumptions on the prior discussed above [Dearden eta/., 1999].

3 Bayesian Imitation

In multiagent settings, observations of other agents can be used in addition to prior beliefs and personal experience to improve an agent's model of its environment. These obser­ vations can have enormous impact when they provide infor­ mation to an agent about parts of the state space it has not yet visited. The information can be used to bias exploration to­ wards the most promising regions of state space and thereby reduce exploration costs and speed convergence dramatically.

The flexibility of the Bayesian formulation leads to an ele­ gant and principled mechanism for incorporating these obser­ vations into the agent's model updates. Following Price and Boutilier 1999, we assume two agents, a knowledgeable men­ tor m and a naive observer o, acting simultaneously, but in­ dependently, in a fixed environment. 1 Like the observer, the mentor too is controlling an MOP (S, Am, Rm, D) with the same underlying state space and dynamics (that is, for any ac­ tion a E A o n Am, the dynamics are identical). The assump­ tion that the two agents have the same state space is not criti­ cal: more important is that there is some analogical mapping between the two [Nehaniv and Dautenhahn, 1998]. We as­ sume full observability of the mentor's state space; but we do not assume the observer can identify the actions taken by the mentor-it simply observes state transitions.

1 We assume that the agents are performing non-interacting tasks.

We make two additional assumptions regarding the men­ tor's dynamics: the mentor implements a stationary pol­ icy 7rm, which induces a Markov chain Prm(s , s') Pr(s, 1r~, s'); and for each action 1r~ taken by the mentor, there exists an action a E A0 such that the distributions Pr(·Js, a) and Pr(-Js, 1r~) are the same. This latter assump­ tion is the homogeneous action assumption and implies that the observer can duplicate the mentor's policy. 2 As a con­ sequence we can treat the dynamics D as the same for both agents. Note that we do not assume that the learner knows a priori which of its actions duplicates the mentor's (for any given states), nor that the observer wants to duplicate this pol­ icy (as the agents may have different objectives) .

Since the learner can observe the mentor's transitions (though not its actions directly), it can form estimates of the mentor's Markov chain, along with estimates of its own MOP (transition probabilities and reward function). In [Price and Boutilier, I999], this estimate is used to augment the normal Bellman backup, treating the observed distribution Pr( s, ·) as a model of an action available to the observer. Imitators using augmented backups based on their observations of a mentor often learn much more quickly, especially if the mentor's re­ ward function or parts of its policy overlap with that of the ob­ server. Techniques like interval estimation [Kaelbling, 1993] can be used to suppress augmented backups where their value has low "confidence."

In the Bayesian approach, the observer incorporates obser­ vations of the mentor directly into an augmented model of its environment. Let Hm denote the history of mentor state tran­ sitions observed by the learner. As above, H 0 and A 0 repre­ sents the observer's state and action history respectively. Fig­ ure I illustrates the sources of information available to the im­ itator with which to constrain its beliefs about D, and their probabilistic dependence. While the observer knows its own action history, A 0 , it has no direct knowledge of the actions taken by the mentor: at best it may have (often weak) prior knowledge about the mentor's policy 7rm. The learner's be­ liefs over D can then be updated w.r.t. the joint observations:

2 The homogeneous action assumption can be relaxed [Price and Boutilier, 2001]. Essentially, the observer hypothesizes that viola­ tions can be "repaired" using a local search for a short sequence of actions that roughly duplicates a short subsequence of the mentor's actions. If a repair cannot be found, the observer discards the mentor influence (at this point in state space).

We assume that the prior P(D) has the factored Dirichlet form described above. Without mentor influence, a Ieamer can maintain its posterior in the same factored form, updating each component of the model P(Ds,a) independently. Unfor­ tunately, complications arise due to the unobservability of the mentor's actions. We show, however, that the model update in Eq. 2 can still be factored into convenient terms.

We derive a factored update model for P(D 8 ·a) describ­ ing the dynamics at state s under action a by considering two cases. In case one, the mentor's unknown action 1r 8 could be different than the action a. In this case, the model fuctor ns,a would be independent of the mentor's history, and we can em­ ploy the standard Bayesian update Eq. 1 without regard for the mentor. In case two, the mentor action 1r;, is in fact the same as the observer's action a. Then the mentor observations are relevant to the update of P(D 8 ·a ):

Let n ·,a be the prior parameter vector for P(D··a), and c~·a denote the counts of observer transitions from state s via action a, and c;, the counts of the mentor transitions from state s. The posterior augmented model factor density P(D 8 ·aiH~·a,H:n_,7r;, =a) isthenaDirichletwithparame­ ters ns ,a + c~·a + c;,; that is, we simply update with the sum of the observer and mentor counts:

Since the observer does not know the mentor's action we compute the expectation w.r.t. these two cases:

This allows a factored update of the usual conjugate form, but where the mentor counts c;, are distributed across all actions, weighted by the posterior probability that the mentor's policy chooses that action at state s. 3 .

With a mechanism to calculate the posterior over the men­ tor's policy, Eq. 3 provides a complete factor~d update rule for incorporating evidence from observed mentors by a Bayesian model-based RL agent. To tackle this last problem-that of updating our beliefs about the mentor's policy-we have:

If we assume that the prior over the mentor's ~olicy is fac­ tored in the same way as the prior over models~that is, we have independent distributions Pr( 1r;,) over Am for each s­ this update can be factored as well, with history elements at state s being the only ones relevant to computing the posterior over 1r m ( s). We still have the difficulty of evaluating the in­ tegral over models. Following Dearden eta/. 1999, we tackle this by sampling models to estimate this quantity. Specifically, we sample models jy,a from the factored Dirichlet P(D··a iH~·a) over V. 4 Given a specific sample iJs,a, with par~meter vector n 8 ,a , and observed counts c;,, the likelihood of n s,a is:

3 Th is assumes that at least one of the observer's actions is equiv­ alent to the mentor's, but our model can be generalized to the het­ erogeneous case. An additional term is required to represent "none of the above".

We can combine the expression for expected model fac­ tor probability in Eq. 3 with our expression for mentor policy likelihood in Eq. 5 to obtain a tractable algorithm for updating the observer's beliefs about the dynamics model D based on its own experience, and observations of the mentor. 5 .

A Bayesian imitator thus proceeds as follows. At each stage, it observes its own state transition and that of the men­ tor, using each to update its density over models as just de­ scribed. Efficient methods are used to update the agent's value function. Using this updated value function, it selects a suit­ able action, executes it, and repeats the cycle.

Like any RL agent, an imitator requires a suitable explo­ ration mechanism. In the Bayesian exploration model [Dear­ den et a/. , 1999 ], the uncertainty about the effects of actions is captured by a Dirichlet, and is used to estimate a distribu­ tion over possible Q-values for each state-action pair. 6 No­ tions such as value of information can then be used to approx­ imate the optimal exploration policy. This method is compu­ tationally demanding, but total reward including reward cap­ tured during training is usually much better than that provided by heuristic techniques. Bayesian exploration also eliminates the parameter tuning required by methods like E-greedy, and adapts locally and instantly to evidence. These facts makes it a good candidate to combine with imitation.

4 Experiments

In this section we attempt to empirically characterize the applicability and expected benefits of Bayesian imitation through several experiments. Using domains from the liter­ ature and two unique domains, we compare Bayesian imi­ tation to non-Bayesian imitation [Price and Boutilier, 1999], and to several standard model-based RL (non-imitating) tech­ niques, including Bayesian exploration, prioritized sweeping and complete Bellman backups. We also investigate how Bayesian exploration combines with imitation.

First, we describe the agents used in our experiments. The Oracle employs a fixed policy optimized for each domain, providing both a baseline and a source of expert behavior for the observers. The EGBS agent combines E-greedy ex­ ploration (EG) with a full Bellman backup (i.e., sweep) at each time step. It provides an example of a generic model­ based approach to learning. The EGPS agent is a model-based RL agent, using E-greedy (EG) exploration with prioritized sweeping (PS). EGPS use fewer backups, but applies them where they are predicted to do the most good. EGPS does not have a fixed backup policy, so it can propagate value multiple steps across the state space in situations where EGBS would not. The BE agent employs Bayesian exploration (BE) with prioritized sweeping for backups. BEBI combines Bayesian exploration (BE) with Bayesian imitation (BI). EGBI com­ bines E-greedy exploration (EG) with Bayesian imitation (BI). The EGNBI agent combines E-greedy exploration with non­ Bayesian imitation.

4 Sampling is efficient as only one local model needs to be resam­ pled at any time step.

5 Scaling techniques such as those used in HMM's may be re­ quired to prevent underflow in the term (ns ,a,t)(c:,.;') in Eq. 5.

6 The Q-value distribution changes very little with each update and can be repaired efficiently using prioritized sweeping. In fact, the Bayesian learner is cheaper to run than a full Bellman backup over all states.

In each experiment, agents begin at the start state. The agents do not interact within the state space. When an agent achieves the goal, it is reset to the beginning. The other agents continue unaffected. Each agent has a fixed number of steps (which may be spread over varying numbers of runs) in each experiment. In each domain, agents are given locally uniform priors (i.e., every action has an equal probability of resulting in any of the local neighbouring states; e.g., in a grid world there are 8 neighbours). Imitators observe the expert oracle agent concurrently with their own exploration. Results are re­ ported as the total reward collected in the last 200 steps. This sliding window integrates the rewards obtained by the agent making it easier to compare performance of various agents. During the first 200 steps, the integration window starts off empty causing the oracle's plot to jump from zero to optimal in the first 200 steps. The Bayesian agents use 5 sampled MDPs for estimating Q-value distributions and 10 samples for esti­ mating the mentor policy from the Dirichlet distribution. Ex­ ploration rates forE-greedy agents were tuned for each exper­ imental domain.

Our first test of the agents was on the "Loop" and "Chain" examples (designed to show the benefits of Bayesian explo­ ration), taken from [Dearden eta/., 1999]. In these experi­ ments, the imitation agents performed more or less identically to the optimal oracle agent and no separation could be seen amongst the imitators.

Using the more challenging "Flag World" domain [Dearden et a/., 1999 ], we see meaningful differences in performance amongst the agents. In FlagWorld, shown in Figure 2, the agent starts at state S and searches for the goal state Gl. The agent may pick up any of three flags by visiting states Fl, F2 and F3. Upon reaching the goal state, the agent receives I point for each flag collected. Each action (N,E,S,W) suc­ ceeds with probability 0.9 if the corresponding direction is clear, and with probability 0.1 moves the agent perpendicu­ lar to the desired direction. Figure 3 shows the reward col­ lected in over the preceding 200 steps for each agent. The Or­ acle demonstrates optimal performance. The Bayesian imita­ tor using Bayesian exploration (BEBI) achieves the quickest convergence to the optimal solution. The E-greedy Bayesian imitator (EGBI) is next, but is not able to exploit informa­ tion locally as well as BEBI. The non-Bayesian imitator (EG­ NBI) does better than the unassisted agents early on but fails to find the optimal policy in this domain. A slower ex­ ploration rate decay would allow the agent to find the opti­ mal policy, but would also hurt its early performance. The non-imitating Bayesian explorer fares poorly compared to the Bayesian imitators, but outperforms the remaining agents, as it exploits prior knowledge about the connectivity of the do­ main. The other agents show poor performance (though with high enough exploration rates they would converge eventu­ ally). We conclude that Bayesian imitation makes the best use of the information available to the agents, particularly when combined with Bayesian exploration.

We altered the Flag World domain so that the mentor and the learners had different objectives. The goal of the expert Ora­ cle remained at location G 1, while the learners had goal loca­ tion G2 (Figure 2). Figure 4 shows that transfer due to imita­ tion is qualitatively similar to the case with identical rewards. We see that imitation transfer is robust to modest differences in mentor and imitator objectives. This is readily explained by the fact that the mentor's policy provides model information over most states in the domain, which can be employed by the observer to achieve its own goals.

The tutoring domain requires agents to schedule the presen­ tation of simple patterns to human learners in order to min­ imize training time. To simplify our experiments, we have the agents teach a simulated student. The student's perfor­ mance is modeled by independent, discretely approximated, exponential forgetting curves for each concept. The agent's action will be its choice of concept to present. The agent re­ ceives a reward when the student's forgetting rate has been reduced below a predefined threshold for all concepts. Pre­ senting a concept lowers its forgetting rate, leaving it unpre­ sented increases its forgetting rate. Our model is too simple to serve as a realistic cognitive model of a student, but provides a qualitatively different problem to tackle. We note that the action space grows linearly with the number of concepts, and the state space exponentially.

The results presented in Figure 5 are based on the presen­ tation of 5 concepts to a student. (EGBS has been left out as it is time-consuming and generally fares poorly.) We see that all of the imitators learn quickly, but with the Bayesian imita­ tors BEBI and EGBI outperformingEGNBI (which converges to a suboptimal policy). 7 The generic Bayesian agent (BE) also chooses a suboptimal solution (which often occurs in BE agents if its priors prevent adequate exploration). Thus, we see that imitation mitigates one of the drawbacks of Bayesian exploration: mentor observations can be used to overcome misleading priors. We see also that Bayesian imitation can also be applied to practical problems with factored state and action spaces and non-geometric structure.

The next domain provides further insight into the combina­ tion of Bayesian imitation and Bayesian exploration. In this grid world (Figure 6), agents can move south only in the first column. In this domain, the optimal Oracle agent proceeds due south to the bottom corner and then east across to the goal. The Bayesian explorer (BE) chooses a path based on its prior beliefs that the space is completely connected. The agent can easily be guided down one of the long "tubes" in this sce­ nario, only to have to retrace it steps. The results in this do­ main, shown in Figure 7, clearly differentiate the early per­ formance of the imitation agents (BEBI, EGBI and EGNBI) from the Bayesian explorer (BE) and other independent learn­ ers. The initial value function constructed from the learner's prior beliefs about the connectivity in the grid world lead it to over-value many of the states that lead to a dead end. This results in a costly misdirection of exploration and poor perfor­ mance. We see that the ability of the Bayesian imitator BEBI to adapt to the local quality of information allows it to ex­ ploit the additional information provided by the mentor more quickly than agents using generic exploration strategies like E-greedy. Again, mentor information is used to great effect to overcome misleading priors.

7 Increasing exploration allows EGNBI to find the optimal policy, but further depresses short term performance.

5 Conclusions

Bayesian imitation, like the non-Bayesian implementation of implicit imitation, accelerates reinforcement learning in the presence of other agents with relevant knowledge without re­ quiring either explicit communication with or the cooperation of these other agents. The Bayesian formulation is built on an elegant pooling mechanism which optimally combines prior knowledge, model observations from the imitator's own expe­ rience and model observations derived from other agents. The combination of Bayesian imitation with Bayesian exploration eliminates parameter tuning and yields an agent that rapidly exploits mentor observations to reduce exploration and in­ crease exploitation. In addition, imitation often overcomes one of the drawbacks of Bayesian exploration, the possibil­ ity of converging to a suboptimal policy due to misleading priors. Bayesian imitation can easily be extended to multiple mentors, and though we did not present the derivation here, it can also be extended to partially observable environments with known state spaces. Though the Bayesian formulation is difficult to implement directly, we have shown that reasonable approximations exist that result in tractable algorithms.

There are several very promising areas of future research that can benefit from the current formulation of Bayesian imi­ tation. One obvious need is to extend the model to the hetero­ geneous action setting by incorporating the notions offeasibil­ ity testing and repair described in [Price and Boutilier, 2001]. We are particularly excited by the prospects of its generaliza­ tion to richer environmental and interaction models. We have also derived one possible mechanism for using the Bayesian approach in domains with continuous attributes. We hope to extend this work to include methods for discovering corre­ spondences between the state and action spaces of various agents. We also plan to introduce game-theoretic considera­ tions into imitation so that agents can learn solutions to inter­ acting tasks from experts and reason about both the reward­ oriented aspects of their action choices as well as the infor­ mation it reveals to others.

Acknowledgements

This research was supported by the Natural Sciences and En­ gineering Research Council and IRIS.