{'fraction_non_alphanumeric': 0.04572424761438708, 'fraction_numerical': 0.012967947149498409, 'mean_word_length': 4.573035622975968, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A General Framework for Interacting Bayes-Optimally with Self-Interested Agents using Arbitrary Parametric Model and Model Prior

Recent advances in Bayesian reinforcement learning (BRL) have shown that Bayes-optimality is theoretically achievable by modeling the environment's latent dynamics using Flat-Dirichlet-Multinomial (FDM) prior. In self-interested multi-agent environments, the transition dynamics are mainly controlled by the other agent's stochastic behavior for which FDM's independence and modeling assumptions do not hold. As a result, FDM does not allow the other agent's behavior to be generalized across different states nor specified using prior domain knowledge. To overcome these practical limitations of FDM, we propose a generalization of BRL to integrate the general class of parametric models and model priors, thus allowing practitioners' domain knowledge to be exploited to produce a fine-grained and compact representation of the other agent's behavior. Empirical evaluation shows that our approach outperforms existing multi-agent reinforcement learning algorithms.


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 struc-tured 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).

Modeling the Other Agent
In our proposed Bayesian modeling paradigm, the opponent's 1 behavior is modeled as a set of probabilities p v sh (λ) Pr(v|s, h, λ) for selecting action v in state s conditioned on the history h {s i , u i , v i } d i=1 of d latest interactions where u i is the action taken by our agent in the i-th step. These distributions are parameterized by λ, which abstracts the ac-tual 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 p v sh (λ) θ 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).
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: (1) Lets = (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 thats = 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 withs. In this case, (1) can be re-written as (2) The key difference between our Bayesian modeling paradigm and FDM [Poupart et al., 2006] is that we do not require b(λ) and p v s (λ) 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 b v s 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 can also be represented exactly in parametric form. Proof Sketch. From (2), we can prove by induction on n that and δ sv is the Kronecker delta function that returns 1 if s = s i and v = v i , and 0 otherwise 2 . 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).

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 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 r s (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 p uv 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 {p v s (λ)} 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 p v s (λ)r s (u, v)|b] and the posterior belief state b v s (λ), 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 V s (b): 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 → ∞: Theorem 3 The optimal value function V k s (b) for k steps-togo can be represented by a finite set Γ k s of α-functions: Simply put, these results imply that the optimal value V s in (5) can be approximated arbitrarily closely by a finite set Γ k s 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, Γ k s 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 Appendix A for a detailed proof. Specifically, given {Γ k s } s such that (6) holds for k, it follows (see Appendix A) that where it follows that (6) also holds for k + 1. As a result, the optimal policy π * (b) can be derived directly from these α-functions by π Thus, constructing Γ k+1 s from the previously constructed sets {Γ k s } 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 {Γ k s } 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 Γ k s of α-functions α j s for j = 1, . . . , |Γ k s |: where Φ i ∈ Φ. So, each α-function α j s can be compactly represented by a finite set of parameters {c i } m i=1 3 . Proof Sketch. We will prove (9) by induction on k 4 . Supposing (9) holds for k. Setting j = t s v in (9) which is then plugged into (8) to yield , and the coefficients c v = r s (u, v) and c v s i = φp uv s (s )c i . It is easy to see that Ψ v ∈ Φ and Ψ v s 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].

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 Γ k s 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: BACKUP(s, k + 1) 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 V s 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) (11). The practicality of our approach therefore depends crucially on how these issues are resolved, as described next.

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 B s = {b 1 s , b 2 s , · · · , 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 b i s can also be written as where b is the initial prior belief, η = 1/ Φ i s , b , and Φ i s ∈ Φ. For convenience, these {Φ i s } i=1,...,|Bs| are selected as basis functions. Specifically, after each PB-BACKUP operation, each α s ∈ Γ k s is projected onto the function space defined by {Φ i s } 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 B s : This can be done analytically by letting ∂J(α s ) ∂c i = 0 and solving for c i , which is equivalent to solving a linear sys- Note that this projection works directly with the values α s , b j s 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 B s = b 1 s , b 2 s , · · · , b |Bs| s need to be maintained. In particular, the values of g, b i s i=1,...,|Bs| can be estimated as follows: where λ j n j=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(|B s |n).
Since the sampling of {b i s }, {λ j } and the computation of can be performed in advance, this O(|B s |n) cost is further reduced to O(n), which makes the action selection incur O(|B s |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 V s incurred by BPVI [Chalkiadakis and Boutilier, 2003]. Also, note that since the offline computational costs in steps 1 to 4 of PB-BACKUP(B s , 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, |B s |), the optimal policy can be approximated in polynomial time.

Experiments and Discussion
In this section, a realistic scenario of intersection navigation is modeled as a stochastic game [Wang et al., 2012]; 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 {P A , P B , S A , S B } specifying the current positions (P ) and velocities (S) of A and B, respectively. In addition, our vehicle (A) can either accelerate (+1 m/s 2 ), decelerate (−1 m/s 2 ), or maintain its speed (+0 m/s 2 ) 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/s 2 , 3 m/s 2 ], deceleration d ∈ [−3 m/s 2 , −0.5 m/s 2 ], 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 P X 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/S X ). 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: 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.

Related Works
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 anbest response (i.e., optimality) against a class of adaptive, bounded-memory opponents while simultaneously guaran-teeing 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, 2013]. Interested readers are referred to [Chalkiadakis and Boutilier, 2003] and Appendix C 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.

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, 2013]. To this end, we have successfully bridged the gap in applying BRL to self-interested multi-agent settings.
Surprisingly, this equation specifies exactly the α-vector back-up operation for the discrete version of (5): whereb is the discrete distribution over the set of samples {λ j } j (i.e., jb (λ j ) = 1). This implies that by choosing {Ψ i (λ)} i as our basis functions, finding the corresponding "projected" solution for (5) is identical to solving (27), which can be easily implemented using any of the existing discrete POMDP solvers (e.g., [Pineau et al., 2003]).

C Additional Experiments
This section provides additional evaluations of our proposed I-BRL framework, in comparison with existing works in MARL, through a series of stochastic games which are adapted and simplified from the testing benchmarks used in [Wang et al., 2012;Poupart et al., 2006]. In particular, I-BRL is evaluated in two small yet typical application domains that are widely used in the existing works (Sections C.1, C.2).

C.1 Multi-Agent Chain World
In this problem, the system consists of a chain of 5 states and 2 agents; each agent has 2 actions {a, b}. In each stage of interaction, both agents will move one step forward or go back to the initial state depending on whether they coordinate on action a or b, respectively [Poupart et al., 2006]. In particular, the agents will receive an immediate reward of 10 for coordinating on a in the last state and 2 for coordinating on b in any state except the first one. Otherwise, the agents will remain in the current state and get no reward (Fig. 3). After each step, their payoffs are discounted by a constant factor of 0 < φ < 1. In this experiment, we compare the performance of I-BRL with the state-of-the-art frameworks in MARL which include BPVI [Chalkiadakis and Boutilier, 2003], Hyper-Q [Tesauro, 2003], and Meta-Strategy [Powers and Shoham, 2005]. Among these works, BPVI is the most relevant to I-BRL (Section 1). Hyper-Q simply extends Q-learning into the context of multi-agent learning. Meta-Strategy, by default, plays the best response to the empirical estimation of the opponent's behavior and occasionally switches to the maximin strategy when its accumulated reward falls below the maximin value of the game. In particular, we compare the average performance of these frameworks when tested against 100 different opponents whose behaviors are modeled as a set of probabilities θ s = {θ v s } v ∼ Dir({n v s } v ) (i.e., of selecting action v in state s). These opponents are independently and randomly generated from these Dirichlet distributions with the parameters n v s = 1/|V |. Then, against each opponent, we run 20 simulations (h = 100 steps each) to evaluate the performance R of each framework. The results show that I-BRL significantly outperforms the others (Fig. 4a).