A General Framework for Interacting Bayes-Optimally with Self-Interested Agents using Arbitrary Parametric Model and Model Prior

1 Introduction

In reinforcement learning (RL), an agent faces a dilemma between acting optimally with respect to the current, possibly incomplete knowledge of the environment (i.e., exploitation) vs. acting sub-optimally to gain more information about it (i.e., exploration). Model-based Bayesian reinforcement learning (BRL) circumvents such a dilemma by considering the notion of Bayes-optimality [Duff, 2003]: A Bayesoptimal policy selects actions that maximize the agent's expected utility with respect to all possible sequences of future beliefs (starting from the initial belief) over candidate models of the environment. Unfortunately, due to the large belief space, the Bayes-optimal policy can only be approximately derived under a simple choice of models and model priors. For example, the Flat-Dirichlet-Multinomial (FDM) prior [Poupart et al., 2006] assumes the next-state distributions for each action-state pair to be modeled as independent multinomial distributions with separate Dirichlet priors. Despite its common use to analyze and benchmark algorithms, FDM can perform poorly in practice as it often fails to exploit the structured information of a problem [Asmuth and Littman, 2011; Araya-Lopez et al., 2012].

To elaborate, a critical limitation of FDM lies in its independence assumption driven by computational convenience rather than scientific insight. We can identify practical examples in the context of self-interested multi-agent RL (MARL) where the uncertainty in the transition model is mainly caused by the stochasticity in the other agent's behavior (in different states) for which the independence assumption does not hold (e.g., motion behavior of pedestrians [Natarajan et al., 2012a; 2012b]). Consider, for example, an application of BRL in the problem of placing static sensors to monitor an environmental phenomenon: It involves actively selecting sensor locations (i.e., states) for measurement such that the sum of predictive variances at the unobserved locations is minimized. Here, the phenomenon is the "other agent" and the measurements are its actions. An important characterization of the phenomenon is that of the spatial correlation of measurements between neighboring locations/states [Low et al., 2007; 2008; 2009; 2011; 2012; Chen et al., 2012; Cao et al., 2013], which makes FDM-based BRL extremely ill-suited for this problem due to its independence assumption.

Secondly, despite its computational convenience, FDM does not permit generalization across states [Asmuth and Littman, 2011], thus severely limiting its applicability in practical problems with a large state space where past observations only come from a very limited set of states. Interestingly, in such problems, it is often possible to obtain prior domain knowledge providing a more "parsimonious" structure of the other agent's behavior, which can potentially resolve the issue of generalization. For example, consider using BRL to derive a Bayes-optimal policy for an autonomous car to navigate successfully among human-driven vehicles [Hoang and Low, 2012; 2013b] whose behaviors in different situations (i.e., states) are governed by a small, consistent set of latent parameters, as demonstrated in the empirical study of Gipps [1981]. By estimating/learning these parameters, it is then possible to generalize their behaviors across different states. This, however, contradicts the independence assumption of FDM; in practice, ignoring this results in an inferior performance, as shown in Section 4. Note that, by using parameter tying [Poupart et al., 2006], FDM can be modified to make the other agent's behavior identical in different states. But, this simple generalization is too restrictive for real-world problems like the examples above where the other agent's behavior in different states is not necessarily identical but related via a common set of latent "non-Dirichlet" parameters.

Consequently, there is still a huge gap in putting BRL into practice for interacting with self-interested agents of unknown behaviors. To the best of our knowledge, this is first investigated by Chalkiadakis and Boutilier [2003] who offer a myopic solution in the belief space instead of solving for a Bayes-optimal policy that is non-myopic. Their proposed BPVI method essentially selects actions that jointly maximize a heuristic aggregation of myopic value of perfect information [Dearden et al., 1998] and an average estimation of expected utility obtained from solving the exact MDPs with respect to samples drawn from the posterior belief of the other agent's behavior. Moreover, BPVI is restricted to work only with Dirichlet priors and multinomial likelihoods (i.e., FDM), which are subject to the above disadvantages in modeling the other agent's behavior. Also, BPVI is demonstrated empirically in the simplest of settings with only a few states.

Furthermore, in light of the above examples, the other agent's behavior often needs to be modeled differently depending on the specific application. Grounding in the context of the BRL framework, either the domain expert struggles to best fit his prior knowledge to the supported set of models and model priors or the agent developer has to re-design the framework to incorporate a new modeling scheme. Arguably, there is no free lunch when it comes to modeling the other agent's behavior across various applications. To cope with this difficulty, the BRL framework should ideally allow a domain expert to freely incorporate his choice of design in modeling the other agent's behavior.

Motivated by the above practical considerations, this paper presents a novel generalization of BRL, which we call Interactive BRL (I-BRL) (Section 3), to integrate any parametric model and model prior of the other agent's behavior (Section 2) specified by domain experts, consequently yielding two advantages: The other agent's behavior can be represented (a) in a fine-grained manner based on the practitioners' prior domain knowledge, and (b) compactly to be generalized across different states, thus overcoming the limitations of FDM. We show how the non-myopic Bayes-optimal policy can be derived analytically by solving I-BRL exactly (Section 3.1) and propose an approximation algorithm to compute it efficiently in polynomial time (Section 3.2). Empirically, we evaluate the performance of I-BRL against that of BPVI [Chalkiadakis and Boutilier, 2003] using an interesting traffic problem modeled after a real-world situation (Section 4).

2 Modeling the Other Agent

In our proposed Bayesian modeling paradigm, the opponent's 1 behavior is modeled as a set of probabilities pvsh (λ) ≜ Pr(v|s, h, λ) for selecting action v in state s conditioned on the history h ≜ {si, ui, vi}di=1 of d latest interactions where ui is the action taken by our agent in the i-th step. These distributions are parameterized by λ, which abstracts the actual parametric form of the opponent's behavior; this abstraction provides practitioners the flexibility in choosing the most suitable degree of parameterization. For example, λ can simply be a set of multinomial distributions λ ≜ {θv sh } such that pvsh (λ) ≜ θv sh if no prior domain knowledge is available. Otherwise, the domain knowledge can be exploited to produce a fine-grained representation of λ; at the same time, λ can be made compact to generalize the opponent's behavior across different states (e.g., Section 4).

1 For convenience, we will use the terms the "other agent" and "opponent" interchangeably from now on.

The opponent's behavior can be learned by monitoring the belief b(λ) ≜ Pr(λ) over all possible λ. In particular, the belief (or probability density) b(λ) is updated at each step based on the history h ◦ 〈s, u, v〉 of d + 1 latest interactions (with 〈s, u, v〉 being the most recent one) using Bayes' theorem:

Let ¯ s = (s, h) denote an information state that consists of the current state and the history of d latest interactions. When the opponent's behavior is stationary (i.e., d = 0), it follows that ¯ s = s. For ease of notations, the main results of our work (in subsequent sections) are presented only for the case where d = 0 (i.e., ¯ s = s); extension to the general case just requires replacing s with ¯ s. In this case, (1) can be re-written as

The key difference between our Bayesian modeling paradigm and FDM [Poupart et al., 2006] is that we do not require b(λ) and pvs (λ) to be, respectively, Dirichlet prior and multinomial likelihood where Dirichlet is a conjugate prior for multinomial. In practice, such a conjugate prior is desirable because the posterior bvs belongs to the same Dirichlet family as the prior b, thus making the belief update tractable and the Bayes-optimal policy efficient to be derived. Despite its computational convenience, this conjugate prior restricts the practitioners from exploiting their domain knowledge to design more informed priors (e.g., see Section 4). Furthermore, this turns out to be an overkill just to make the belief update tractable. In particular, we show in Theorem 1 below that, without assuming any specific parametric form of the initial prior, the posterior belief can still be tractably represented even though they are not necessarily conjugate distributions. This is indeed sufficient to guarantee and derive a tractable representation of the Bayes-optimal policy using a finite set of parameters, as shall be seen later in Section 3.1.

Theorem 1 If the initial prior b can be represented exactly using a finite set of parameters, then the posterior b′ conditioned on a sequence of observations {(si, vi)}n′ i=1 can also be represented exactly in parametric form.

Proof Sketch. From (2), we can prove by induction on n′ that

where ψv s ≜ ∑n′ i=1 δsv(si, vi) and δsv is the Kronecker delta function that returns 1 if s = si and v = vi, and 0 otherwise 2 .

2 Intuitively, Φ(λ) can be interpreted as the likelihood of observing each pair (s, v) for ψv s times while interacting with an opponent whose behavior is parameterized by λ.

From (3), it is clear that b′ can be represented by a set of parameters {ψv s }s,v and the finite representation of b. Thus, belief update is performed simply by incrementing the hyperparameter ψv s according to each observation (s, v). □

3 Interactive Bayesian RL (I-BRL)

In this section, we first extend the proof techniques used in [Poupart et al., 2006] to theoretically derive the agent's Bayes-optimal policy against the general class of parametric models and model priors of the opponent's behavior (Section 2). In particular, we show that the derived Bayes-optimal policy can also be represented exactly using a finite number of parameters. Based on our derivation, a naive algorithm can be devised to compute the exact parametric form of the Bayesoptimal policy (Section 3.1). Finally, we present a practical algorithm to efficiently approximate this Bayes-optimal policy in polynomial time (with respect to the size of the environment model) (Section 3.2).

Formally, an agent is assumed to be interacting with its opponent in a stochastic environment modeled as a tuple (S, U, V, {rs}, {puv s }, {pvs (λ)}, φ) where S is a finite set of states, U and V are sets of actions available to the agent and its opponent, respectively. In each stage, the immediate payoff rs(u, v) to our agent depends on the joint action (u, v) ∈ U × V and the current state s ∈ S. The environment then transitions to a new state s′ with probability puv s (s′ ) ≜ Pr(s′ |s, u, v) and the future payoff (in state s′ ) is discounted by a constant factor 0 < φ < 1, and so on. Finally, as described in Section 2, the opponent's latent behavior {pvs (λ)} can be selected from the general class of parametric models and model priors, which subsumes FDM (i.e., independent multinomials with separate Dirichlet priors).

Now, let us recall that the key idea underlying the notion of Bayes-optimality [Duff, 2003] is to maintain a belief b(λ) that represents the uncertainty surrounding the opponent's behavior λ in each stage of interaction. Thus, the action selected by the learner in each stage affects both its expected immediate payoff Eλ[∑v pvs (λ)rs(u, v)|b] and the posterior belief state bvs (λ), the latter of which influences its future payoff and builds in the information gathering option (i.e., exploration). As such, the Bayes-optimal policy can be obtained by maximizing the expected discounted sum of rewards Vs(b):

where 〈a, b〉 ≜ ∫λ a(λ)b(λ)dλ. The optimal policy for the learner is then defined as a function π∗ that maps the belief b to an action u maximizing its expected utility, which can be derived by solving (5). To derive our solution, we first re-state two well-known results concerning the augmented belief-state MDP in single-agent RL [Poupart et al., 2006], which also hold straight-forwardly for our general class of parametric models and model priors.

Theorem 2 The optimal value function V k for k steps-to-go converges to the optimal value function V for infinite horizon as k → ∞: ‖V - V k+1 ‖∞ ≤ φ‖V - V k ‖∞ .

Theorem 3 The optimal value function V k s (b) for k steps-togo can be represented by a finite set Γks of α-functions:

Simply put, these results imply that the optimal value Vs in (5) can be approximated arbitrarily closely by a finite set Γks of piecewise linear α-functions αs, as shown in (6). Each αfunction αs is associated with an action uαs yielding an expected utility of αs(λ) if the true behavior of the opponent is λ and consequently an overall expected reward 〈αs, b〉 by assuming that, starting from (s, b), the learner selects action uαs and continues optimally thereafter. In particular, Γks and uαs can be derived based on a constructive proof of Theorem 3. However, due to limited space, we only state the constructive process below. Interested readers are referred to [Hoang and Low, 2013a] for a detailed proof. Specifically, given {Γks }s such that (6) holds for k, it follows (see [Hoang and Low, 2013a]) that

where t ≜ (ts′ v)s′∈S,v∈V with ts′ v ∈ {1, . . . , ∣∣Γks′ ∣∣}, and

such that αts′v s′ denotes the ts′ v-th α-function in Γks′ . Setting Γk+1 s = {αut s }u,t and uαut s = u, it follows that (6) also holds for k + 1. As a result, the optimal policy π∗ (b) can be derived directly from these α-functions by π∗ (b) ≜ uα∗s where α∗ s = argmaxαut s ∈Γk+1 s 〈αut s , b〉 . Thus, constructing Γk+1 s from the previously constructed sets {Γks }s essentially boils down to an exhaustive enumeration of all possible pairs (u, t) and the corresponding application of (8) to compute αut s . Though (8) specifies a bottom-up procedure constructing Γk+1 s from the previously constructed sets {Γks′}s′ of αfunctions, it implicitly requires a convenient parameterization for the α-functions that is closed under the application of (8). To complete this analytical derivation, we present a final result to demonstrate that each α-function is indeed of such parametric form. Note that Theorem 4 below generalizes a similar result proven in [Poupart et al., 2006], the latter of which shows that, under FDM, each α-function can be represented by a linear combination of multivariate monomials. A practical algorithm building on our generalized result in Theorem 4 is presented in Section 3.2.

Theorem 4 Let Φ denote a family of all functions Φ(λ) (4). Then, the optimal value V k s′ can be represented by a finite set Γks′ of α-functions αjs′ for j = 1, . . . , |Γks′ |:

where Φi ∈ Φ. So, each α-function αjs′ can be compactly represented by a finite set of parameters {ci}mi=1 3 .

3 To ease readability, we abuse the notations {ci, Φi}mi=1 slightly: Each αjs′ (λ) should be specified by a different set {ci, Φi}mi=1.

Proof Sketch. We will prove (9) by induction on k4 . Supposing (9) holds for k. Setting j = ts′ v in (9) results in

which is then plugged into (8) to yield

where Ψv(λ) = pvs (λ), Ψvs′ i (λ) = pvs (λ)Φi(λ), and the coefficients cv = rs(u, v) and cvs′ i = φpuv s (s′ )ci. It is easy to see that Ψv ∈ Φ and Ψvs′ i ∈ Φ. So, (9) clearly holds for k+1. We have shown above that, under the general class of parametric models and model priors (Section 2), each α-function can be represented by a linear combination of arbitrary parametric functions in Φ, which subsume multivariate monomials used in [Poupart et al., 2006]. □

3.1 An Exact Algorithm

Intuitively, Theorems 3 and 4 provide a simple and constructive method for computing the set of α-functions and hence, the optimal policy. In step k + 1, the sets Γk+1 s for all s ∈ S are constructed using (10) and (11) from Γks′ for all s′ ∈ S, the latter of which are computed previously in step k. When k = 0 (i.e., base case), see the proof of Theorem 4 above (i.e., footnote 4). A sketch of this algorithm is shown below:

In the above algorithm, steps 1 and 2 compute the first and second summation terms on the right-hand side of (11), respectively. Then, steps 3 and 4 construct Γk+1 s = {αut s }u,t using (11) over all t and u, respectively. Thus, by iteratively computing Γk+1 s = BACKUP(s, k + 1) for a sufficiently large value of k, Γk+1 s can be used to approximate Vs arbitrarily closely, as shown in Theorem 2. However, this naive algorithm is computationally impractical due to the following issues: (a) α-function explosion - the number of α-functions grows doubly exponentially in the planning horizon length, as derived from (7) and (8): ∣∣Γk+1 s ∣∣ = O([∏s′ ∣∣Γks′ ∣∣]|V | |U|), and (b) parameter explosion - the average number of parameters used to represent an α-function grows by a factor of O(|S||V |), as manifested in (11). The practicality of our approach therefore depends crucially on how these issues are resolved, as described next.

4 When k = 0, (9) can be verified by letting ci = 0.

5A ⊕ B = {a + b|a ∈ A, b ∈ B}.

3.2 A Practical Approximation Algorithm

In this section, we introduce practical modifications of the BACKUP algorithm by addressing the above-mentioned issues. We first address the issue of α-function explosion by generalizing discrete POMDP's PBVI solver [Pineau et al., 2003] to be used for our augmented belief-state MDP: Only the α-functions that yield optimal values for a sampled set of reachable beliefs Bs = {b1s , b2s , · · · , b|Bs| s } are computed (see the modifications in steps 3 and 4 of the PB-BACKUP algorithm). The resulting algorithm is shown below:

Secondly, to address the issue of parameter explosion, each α-function is projected onto a fixed number of basis functions to keep the number of parameters from growing exponentially. This projection is done after each PB-BACKUP operation, hence always keeping the number of parameters fixed (i.e., one parameter per basis function). In particular, since each α-function is in fact a linear combination of functions in Φ (Theorem 4), it is natural to choose these basis functions from Φ6 . Besides, it is easy to see from (3) that each sampled belief bis can also be written as

where b is the initial prior belief, η = 1/〈Φis , b〉, and Φis ∈ Φ. For convenience, these {Φis }i=1,...,|Bs| are selected as basis functions. Specifically, after each PB-BACKUP operation, each αs ∈ Γks is projected onto the function space defined by {Φis }i=1,...,|Bs|. This projection is then cast as an optimization problem that minimizes the squared difference J(αs) between the α-function and its projection with respect to the sampled beliefs in Bs:

This can be done analytically by letting ∂J(αs) ∂ci = 0 and solving for ci, which is equivalent to solving a linear system Ax = d where xi = ci, Aji = ∑|Bs| k=1 〈Φis , bks 〉 〈Φjs , bks 〉 and dj = ∑|Bs| k=1 〈Φjs , bks 〉 〈αs, bks 〉. Note that this projection works directly with the values 〈αs, bjs 〉 instead of the exact parametric form of αs in (9). This allows for a more compact implementation of the PB-BACKUP algorithm presented above: Instead of maintaining the exact parameters that represent each of the immediate functions g, only their evaluations at the sampled beliefs Bs = {b1s , b2s , · · · , b|Bs| s } need to be maintained. In particular, the values of {〈g, bis 〉}i=1,...,|Bs| can be estimated as follows:

6 See Appendix B of Hoang and Low [2013a] for other choices.

where {λj }nj=1 are samples drawn from the initial prior b. During the online execution phase, (14) is also used to compute the expected payoff for the α-functions evaluated at the current belief b′ (λ) = ηΦ(λ)b(λ):

So, the real-time processing cost of evaluating each αfunction's expected reward at a particular belief is O(|Bs|n). Since the sampling of {bis }, {λj } and the computation of {∑|Bs| i=1 ciΦis (λj )} can be performed in advance, this O(|Bs|n) cost is further reduced to O(n), which makes the action selection incur O(|Bs|n) cost in total. This is significantly cheaper as compared to the total cost O(nk|S|2 |U||V |) of online sampling and re-estimating Vs incurred by BPVI [Chalkiadakis and Boutilier, 2003]. Also, note that since the offline computational costs in steps 1 to 4 of PBBACKUP(Bs, s, k+1) and the projection cost, which is cast as the cost of solving a system of linear equations, are always polynomial functions of the interested variables (e.g., |S|, |U|, |V |, n, |Bs|), the optimal policy can be approximated in polynomial time.

4 Experiments and Discussion

In this section, a realistic scenario of intersection navigation is modeled as a stochastic game; it is inspired from a near-miss accident during the 2007 DARPA Urban Challenge. Considering the traffic situation illustrated in Fig. 1 where two autonomous vehicles (marked A and B) are about to enter an intersection (I), the road segments are discretized into a uniform grid with cell size 5 m × 5 m and the speed of each vehicle is also discretized uniformly into 5 levels ranging from 0 m/s to 4 m/s. So, in each stage, the system's state can be characterized as a tuple {PA, PB, SA, SB} specifying the current positions (P ) and velocities (S) of A and B, respectively. In addition, our vehicle (A) can either accelerate (+1 m/s2 ), decelerate (-1 m/s2 ), or maintain its speed (+0 m/s2 ) in each time step while the other vehicle (B) changes its speed based on a parameterized reactive model [Gipps, 1981]:

In this model, the driver's acceleration a ∈ [0.5 m/s2 , 3 m/s2 ], deceleration d ∈ [-3 m/s2 ,-0.5 m/s2 ], reaction time τ ∈ [0.5s, 2s], and imperfection σ ∈ [0, 1] are the unknown parameters distributed uniformly within the corresponding ranges. This parameterization can cover a variety of drivers' typical behaviors, as shown in a preliminary study. For a further understanding of these parameters, the readers are referred to [Gipps, 1981]. Besides, in each time step, each vehicle X ∈ {A, B} moves from its current cell PX to the next cell P ′X with probability 1/t and remains in the same cell with probability 1 - 1/t where t is the expected time to move forward one cell from the current position with respect to the current speed (e.g., t = 5/SX). Thus, in general, the underlying stochastic game has 6×6×5×5 = 900 states (i.e., each vehicle has 6 possible positions and 5 levels of speed), which is significantly larger than the settings in previous experiments. In each state, our vehicle has 3 actions, as mentioned previously, while the other vehicle has 5 actions corresponding to 5 levels of speed according to the reactive model.

The goal for our vehicle in this domain is to learn the other vehicle's reactive model and adjust its navigation strategy accordingly such that there is no collision and the time spent to cross the intersection is minimized. To achieve this goal, we penalize our vehicle in each step by -1 and reward it with 50 when it successfully crosses the intersection. If it collides with the other vehicle (at I), we penalize it by -250. The discount factor is set as 0.99. We evaluate the performance of I-BRL in this problem against 100 different sets of reactive parameters (for the other vehicle) generated uniformly from the above ranges. Against each set of parameters, we run 20 simulations (h = 100 steps each) to estimate our vehicle's average performance 7 R. In particular, we compare our algorithm's average performance against the average performance of a fully informed vehicle (Upper Bound) who knows exactly the reactive parameters before each simulation, a rational vehicle (Exploit) who estimates the reactive parameters by taking the means of the above ranges, and a vehicle employing BPVI [Chalkiadakis and Boutilier, 2003] (BPVI).

The results are shown in Fig. 2a: It can be observed that our vehicle always performs significantly better than both the rational and BPVI-based vehicles. In particular, our vehicle manages to reduce the performance gap between the fully informed and rational vehicles roughly by half. The difference in performance between our vehicle and the fully informed vehicle is expected as the fully informed vehicle always takes the optimal step from the beginning (since it knows the reactive parameters in advance) while our vehicle has to take cautious steps (by maintaining a slow speed) before it feels confident with the information collected during interaction. Intuitively, the performance gap is mainly caused during this initial period of "caution". Also, since the uniform prior over the reactive parameters λ = {a, d, τ, σ} is not a conjugate prior for the other vehicle's behavior model θs(v) = p(v|s, λ), the BPVI-based vehicle has to directly maintain and update its belief using FDM: λ = {θs}s with θs = {θv s }v ∼ Dir({nvs }v) (Section 2), instead of λ = {a, d, τ, σ}. However, FDM implicitly assumes that {θs}s are statistically independent, which is not true in this case since all θs are actually related by {a, d, τ, σ}. Unfortunately, BPVI cannot exploit this information to generalize the other vehicle's behavior across different states due to its restrictive FDM (i.e., independent multinomial likelihoods with separate Dirichlet priors), thus resulting in an inferior performance.

7 After our vehicle successfully crosses the intersection, the system's state is reset to the default state in Fig. 1 (Right).

5 RelatedWorks

In self-interested (or non-cooperative) MARL, there has been several groups of proponents advocating different learning goals, the following of which have garnered substantial support: (a) Stability - in self-play or against a certain class of learning opponents, the learners' behaviors converge to an equilibrium; (b) optimality - a learner's behavior necessarily converges to the best policy against a certain class of learning opponents; and (c) security - a learner's average payoff must exceed the maximin value of the game. For example, the works of Littman [2001], Bianchi et al. [2007], and Akchurina [2009] have focused on (evolutionary) gametheoretic approaches that satisfy the stability criterion in selfplay. The works of Bowling and Veloso [2001], Suematsu and Hayashi [2002], and Tesauro [2003] have developed algorithms that address both the optimality and stability criteria: A learner essentially converges to the best response if the opponents' policies are stationary; otherwise, it converges in self-play. Notably, the work of Powers and Shoham [2005] has proposed an approach that provably converges to an ϵbest response (i.e., optimality) against a class of adaptive, bounded-memory opponents while simultaneously guaranteeing a minimum average payoff (i.e., security) in singlestate, repeated games.

In contrast to the above-mentioned works that focus on convergence, I-BRL directly optimizes a learner's performance during its course of interaction, which may terminate before it can successfully learn its opponent's behavior. So, our main concern is how well the learner can perform before its behavior converges. From a practical perspective, this seems to be a more appropriate goal: In reality, the agents may only interact for a limited period, which is not enough to guarantee convergence, thus undermining the stability and optimality criteria. In such a context, the existing approaches appear to be at a disadvantage: (a) Algorithms that focus on stability and optimality tend to select exploratory actions with drastic effect without considering their huge costs (i.e., poor rewards) [Chalkiadakis and Boutilier, 2003]; and (b) though the notion of security aims to prevent a learner from selecting such radical actions, the proposed security values (e.g., maximin value) may not always turn out to be tight lower bounds for the optimal performance [Hoang and Low, 2013a]. Interested readers are referred to [Chalkiadakis and Boutilier, 2003] and Appendix C of Hoang and Low [2013a] for a detailed discussion and additional experiments to compare performances of I-BRL and these approaches, respectively.

Note that while solving for the Bayes-optimal policy efficiently has not been addressed explicitly in general prior to this paper, we can actually avoid this problem by allowing the agent to act sub-optimally in a bounded number of steps. In particular, the works of Asmuth and Littman [2011] and Araya-Lopez et al. [2012] guarantee that, in the worst case, the agent will act nearly approximately Bayes-optimal in all but a polynomially bounded number of steps with high probability. It is thus necessary to point out the difference between I-BRL and these worst-case approaches: We are interested in maximizing the average-case performance with certainty rather than the worst-case performance with some "high probability" guarantee. Comparing their performances is beyond the scope of this paper.

6 Conclusion

This paper describes a novel generalization of BRL, called I-BRL, to integrate the general class of parametric models and model priors of the opponent's behavior. As a result, I-BRL relaxes the restrictive assumption of FDM that is often imposed in existing works, thus offering practitioners greater flexibility in encoding their prior domain knowledge of the opponent's behavior. Empirical evaluation shows that I-BRL outperforms a Bayesian MARL approach utilizing FDM called BPVI. I-BRL also outperforms existing MARL approaches focusing on convergence (Section 5), as shown in the additional experiments in [Hoang and Low, 2013a]. To this end, we have successfully bridged the gap in applying BRL to self-interested multi-agent settings.

Acknowledgments. This work was supported by SingaporeMIT Alliance Research & Technology Subaward Agreements No. 28 R-252-000-502-592 & No. 33 R-252-000-509-592.