Decision-Making Among Bounded Rational Agents

In an MMDP with $N$ agents, each agent $i$ has its own state space $s^{i}\in\mathcal{S}^{i}$ and action space $a^{i}\in\mathcal{A}^{i}$, where $a^{i}$ and $s^{i}$ denote the state and action of agent $i$; $\mathcal{S}^{i}$ and $\mathcal{A}^{i}$ denote the corresponding spaces. We denote the joint states and actions of all the agents as $S=[s^{1},...,s^{N}]$ and $A=[a^{1},...,a^{N}]$. The agents progress in the environment as follows. At every timestep $t$, all the agents simultaneously execute their actions $A_{t}$ to advance to the next states $S_{t+1}$ according to their stochastic transition function $s^{i}_{t+1}\sim p^{i}(s^{i}_{t+1}|S_{t},A_{t})$. At the same time, they receive rewards $R_{t}=[r_{t}^{1},...,r_{t}^{N}]$, where $r_{t}^{i}=f^{i}_{t}(S_{t},A_{t})$ is the reward function for agent $i$. Each agent’s stochastic transition and reward functions depend on all agents’ states and actions in the system. Under the perfectly rational assumption, the goal for agent $i$ is to find a strategy that maximizes an expected utility function

where $U^{i}(S_{t},\Pi_{t})=\mathbb{E}\Big{[}\sum_{k=t}^{H+t}r^{i}_{t}(S_{k},A_{k})\Big{]}$ is agent $i$’s utility function at $t$; $H$ is planning horizon, and $\Pi_{t}=[\pi_{t}^{1},...,\pi_{t}^{N}]$ denotes the strategy profile for every agent. In this work, we assume that the agents’ strategies take a specific form: a distribution over the action sequence $\mathbf{a}_{t}^{i}\sim\pi_{t}^{i}(\mathbf{a}_{t}^{i}|S_{t},\Pi_{t}^{-i})$, where $\mathbf{a}_{t}^{i}=[a_{t}^{i},...,a_{t+H}^{i}]$ is the action sequence up to horizon $H$ and $\Pi_{t}^{-i}$ is the strategy profile without agent $i$. This policy form is well-suited for most robotics problems because the trajectory induced by the action sequence can be tracked by a low-level controller.

To solve the problem defined in Eq. (1), each agent needs to predict how other agents will behave and respond to each other. For brevity, we will write $\pi^{i}(a_{t}^{i}|S_{t})$ as agent $i$’s strategy and omit the dependency on $\Pi^{-i}$. One possible and common way to predict other agents’ behaviors is by assuming all other agents are perfectly rational, and thus the strategy profile of all the agents reaches the Nash Equilibrium (NE) (if exists) [16], which satisfies the following relationship:

Intuitively, if the agents satisfy the NE, no agent can improve its utility by unilaterally changing its strategy. To compute NE, we can apply a numerical procedure called Iterative Best Response (IBR) [19]. Starting from an initial guess of the strategy profiles of all the agents, we update each agent’s strategy to the best response to the current strategies of all other agents. The above procedure is applied iteratively for each agent until the strategy profile does not change. If every agent is perfectly rational, the robot can use NE strategy profile to predict other agents’ behaviors and act correspondingly.²²2We make a simplifying assumption that there is only one NE in the game.. However, there is a gap between this perfect rational assumption and the real world, as most existing methods can only search the strategy profile in a neighborhood of the initial guess [24, 23] due to computational limits. In the following section, we fill this gap by explicitly formulating this bounded rational solution.

In the standard game-theoretic frameworks, agents are rational, i.e., they optimize their decisions via evaluating an infinite number of action sequences without considering the computational resources. In contrast, we model each agent as bounded rational – it makes decisions that maximize its utility subject to a certain computational constraint. Following the work in information-theoretic bounded rationality [14, 6], this constraint is explicitly defined by the neighborhood of a default policy $q^{i}$. Intuitively, this default policy describes the nominal behavior of the agent. For example, in a driving scenario, the default policy of an aggressive driver may be more likely to drive at a high speed. The agent’s goal is to search for an optimized posterior policy bounded within the neighborhood of $q^{i}$. This size of the neighborhood may reflect the limited computational resources or other practical considerations. In the following, we omit the time subscript $t$ for clarity. We use KL-divergence to characterize this neighborhood

$K_{i}$ is a constant denoting the amount of computation (measured in bits) agent $i$ can deviate from the default policy. Using Lagrange multipliers, we can rewrite the constrained optimization problem in Eq. (3) as an unconstrained one $\pi^{i,*}=\operatorname*{arg\,max}_{\pi^{i}}U^{i}(S,\Pi)-\frac{1}{\beta_{i}}KL(\pi^{i}||q^{i})$, where $\beta_{i}>0$ indicates the rationality level. To see how this bounded-optimal stochastic policy can be computed, we can first observe that the unconstrained problem can be written as

where $\psi^{i}(\mathbf{a}^{i}|\mathbf{s})\propto q^{i}(\mathbf{a}^{i})e^{\beta U(\mathbf{s},\mathbf{a})}$. Since KL-divergence is non-negative, the maximum of $-\frac{1}{\beta}KL(\pi^{i}||\psi^{i})$ is obtained only when $KL(\pi^{i}||\psi^{i})=0$, which means $\pi^{i}=\psi^{i}$. Therefore, the optimal action sequence distribution of agent $i$ (while keeping other agents’ strategies fixed) under the bounded rationality constraint is

where $Z=\int q^{i}(\mathbf{a}^{i})e^{\beta\cdot U^{i}(S,\Pi)}d\mathbf{a}^{i}$ is a normalization constant. This bounded-optimal strategy provides an intuitive and explainable way to trade-off between computation and performance. When $\beta$ increases from $0$ to infinity, the agent becomes more rational and requires more time to compute the optimal behavior. When $\beta_{i}=0$, the bounded-rational policy becomes the prior, meaning agent $i$ has no computational resources to leverage. On the other hand, when $\beta_{i}\rightarrow\infty$, the agent becomes entirely rational and selects the optimal action sequence deterministically. The rationality parameter $\beta$ allows us to model agents with different amounts of computational resources.

Similar to the rational case, our goal is to find the Nash Equilibrium strategy profile for a group of bounded-rational agents whose bounded-optimal policies are defined in Eq. (5). This can be done using the IBR procedure analogous to Section 3. Instead of optimizing the policy in Eq. (1), each bounded-rational agent finds the optimal strategy distribution defined in Eq. (5) while keeping other agents’ strategies fixed. This procedure is carried out for each agent for a fixed number of iterations or until no agent’s stochastic policy changes.

The previous section describes the bounded rationality concept, its integration with the game-theoretic framework, and uses the IBR numerical method to solve for a bounded rational Nash Equilibrium strategy profile. To actually compute the bounded-rational strategies, we need an efficient way to query samples from the distribution in Eq. (5) for each agent. Since it is relatively easier to sample the actions from the default $q^{i}(\mathbf{a}^{i})$, we can use importance sampling to estimate the expectation of the optimal action sequence as the best response for the agent $i$ while keeping others’ actions fixed [2]

where $w(\mathbf{a}^{i}_{t})=\exp\{\beta\sum_{k=t}^{H+t}r^{i}_{t}(S_{k},A_{k})\}$ and $\mathbf{a}^{i}_{t,k}$ denotes the $k^{th}$ sample from the default policy with $N$ samples in total. Similarly, the normalization constant can also be approximated as

At a high level, the importance sampling procedure proceeds as follows. The agents first propose action sequence samples from their default policies $q^{i}_{t}(\mathbf{a}^{i})$ and then assign each sequence a weight $w(\mathbf{a_{t}}^{i})$ indicating its value based on the agents’ utilities and rationality levels. Finally, by combining Eq. (6) and Eq. (7), we can use the weighted average to compute the expected optimal action sequence

To find the bounded-rational Nash Equilibrium strategy profile, we replace the optimization procedure in IBR Eq. (2) using the above importance sampling. One important observation is that the shape of the prior distribution $q^{i}$, the number of samples for evaluation $N$, and the rationality level $\beta$ play essential roles in the final performance. Their relationships will be explored in the experimental section.

In this experiment, we consider the task of navigating a group of aerial vehicles in a 3D space. Each agent’s goal is to swap its position with the diametrically opposite one while avoiding collisions with each other. The distance between each agent and its goal is $6m$. This environment is neither fully cooperative as each agent has a different goal location nor fully competitive because their objectives are not totally reversed (zero-sum). Thus, the agents need to collaborate with each other to avoid blockage in the center and at the same time compete with each other to follow their shortest paths to the goals. The agents are homogeneous in terms of their sizes and physical capabilities. Each agent has a size of $0.125m$ in $x,y,z$ directions (similar to the dimension of Crazyfly drones used in the next section). Similar to [24], we set their transition functions using a deterministic single integrator model with the minimum and maximum speeds as $a_{min}=0m/s$ and $a_{max}=1m/s$. We set a uniform prior $q^{i}(\mathbf{a})=Uniform(a_{min},a_{max})$ as the default policy for all the agents. The number of IBR iterations is set to $10$ as we found that under varying parameters, IBR usually converges to a bounded rational NE strategy at $10$ iterations. In all the simulations, we assume that the rationality levels of all the agents are known to each other. The one-step reward function is the same for each agent and set to penalize collisions and large distances to the goal. We run $50$ times for each simulation with $T=80$ timesteps.

We first show that using the proposed framework agents can naturally reason about the behaviors of others with the same physical capabilities but different rationality levels $\beta$. Since we want to examine how varying $\beta$ affects the performance, we need to ensure that the policy converges to the “optimal” one under the computational constraints. Thus, we sample a large number of trajectories, $5\times 10^{5}$, for policy computation for each agent. In this simulation, we fix other agents’ $\beta=0.05$ and vary one agent’s (called ego agent) $\beta$ from $0.01$ to $0.13$ and compare the travel distances between the robot and other agents (the distance of other agents is averaged). Fig. 11 shows the performance comparison in six and eight agent environments. In general, when the ego has a lower rationality level $\beta$ than other agents, it avoids them by taking a longer path. When all the agents have the same $\beta$, the ego and other agents have a similar performance. As $\beta$ increases, the ego begins to exploit its advantage in computing more rational decisions and taking shorter paths. We also notice that the ego generally performs better with a large $\beta$ when there are more agents in the scene. The trajectories of the six-agent environment for $\beta=0.01$ and $\beta=0.13$ are plotted in Fig 11(a) and Fig 11(b), respectively. When the ego’s $\beta=0.01$ (in the red trajectory), it takes a detour by elevating to a higher altitude to avoid other agents. In contrast, when its $\beta=0.13$, it pushes other agents aside and takes an almost straight path. These results are aligned with Fig. 11. We omit the trajectories of eight agent environments to avoid clutter. The readers are encouraged to watch the videos at https://youtu.be/hzCitSSuWiI

Next, we evaluate the performance of a group of agents with the same $\beta$ to show that the trade-off between the performance and computation can be directly controlled by the rationality level. Since most of the computation occurs when evaluating a large number of sampled trajectories in the proposed importance sampling-based method, we can use the number of evaluated trajectories as a proxy to measure the amount of computation an agent possesses. In Fig. 24, we analyze the relationship between $\beta$ and the computation constraint in the six-agent environment. We can observe that when the computation is limited, i.e., only a small number of action sequences can be evaluated, a larger $\beta$ (more rational) actually hurts the performance. When the more rational agents have the resources to evaluate more trajectories, they travel less distance on average than the less rational groups. This result demonstrates that by controlling the rationality parameter the bounded rational framework can effectively trade-off between optimality and limited computation. In Fig. 22, we also evaluate the number of trajectories that need to be sampled for the method to converge at different rationality levels in four, six, and eight agent environments. The result aligns with the previous observation – in general, when $\beta$ is larger, more trajectories need to be evaluated to converge to “optimal” under the bounded rational constraints. Furthermore, when more agents are present in the environment, the method requires more trajectories to converge.

Finally, we show qualitative trajectory results of the group behaviors under bounded rationality using a fixed $\beta=0.1$ and number of samples $N=5\times 10^{5}$ for each agent in Fig. 4. Additionally, we provide the minimum distances of each agent to other agents in Fig. 3. The result shows that in each environment, the agent can maintain a safe distance $>0.25m$ to avoid collisions.