Recent advancement in reinforcement learning research has witnessed much development on multiagent reinforcement learning (MARL). However, most of the works focus on risk-neutral agents, which may not be suitable for modeling the real world. For example, in investment activities, different investors have different risk preferences depending on their roles in the market. Some act as speculators and are risk-seeking, while others are bound by regulatory constraints and are thus risk-averse. Another example is multi-player online role-playing games, where each of the players can be considered an agent. Whereas some (risk-seeking) players enjoy exploring uncharted regions in the game, others (risk-averse players) prefer to playing in areas that are well explored and come with less uncertainty. It is not hard to see that in the above examples, modeling each agent as uniformly risk-neutral is inappropriate. This naturally calls for a more sophisticated modeling framework that takes into account of heterogeneous risk preferences of agents. In this paper, we study the problem of risk-sensitive MARL under the setting of general-sum Markov games (MGs), a more realistic multi-agent model in which the agents may take different risk preferences.

This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS). These algorithms draw inspiration from foundational concepts in information theory, and are proven to be sample efficient in MARL settings such as two-player zero-sum Markov games (MGs) and multi-player general-sum MGs. For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. The basic algorithm, referred to as MAIDS, employs an asymmetric learning structure where the max-player first solves a minimax optimization problem based on the joint information ratio of the joint policy, and the min-player then minimizes the marginal information ratio with the max-player's policy fixed. Theoretical analyses show that it achieves a Bayesian regret of tilde{O}(sqrt{K}) for K episodes. To reduce the computational load of MAIDS, we develop an improved algorithm called Reg-MAIDS, which has the same Bayesian regret bound while enjoying less computational complexity. Moreover, by leveraging the flexibility of IDS principle in choosing the learning target, we propose two methods for constructing compressed environments based on rate-distortion theory, upon which we develop an algorithm Compressed-MAIDS wherein the learning target is a compressed environment. Finally, we extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.

Multi-agent reinforcement learning (MARL) has achieved re markable empirical successes in solving complicated games involving sequential and strategic d ecision-making across multiple agents ( Vinyals et al., 2019; Brown and Sandholm, 2018; Silver et al., 2016). These achievements have catalyzed many research efforts focusing on developing efficient MARL algorithms in a theoretically principled manner. Specifically, a multi-agent system is ty pically modeled as a general-sum Markov Game (MG) ( Littman, 1994), with the primary aim of efficiently discerning a certain equ ilibrium notion among multiple agents from data collected via online interactions. Some popular equilibrium notions include Nash equilibrium (NE), correlated equ ilibrium (CE), and coarse correlated equilibrium (CCE). However, multi-agent general-sum Markov Games (MGs) bring forth various challenges. In particular, empirical application suffers from the large st ate space. Such a challenge necessitates the use of the function approximation as an effective way to ex tract the essential features of RL problems and avoid dealing directly with the large state spa ce. Yet, adopting function approximation in a general-sum MG brings about additional complexities no t found in single-agent RL or a zero-sum MG.

Multi-agent reinforcement learning has made substantial empirical progresses in solving games with a large number of players. However, theoretically, the best known sample complexity for finding a Nash equilibrium in general-sum games scales exponentially in the number of players due to the size of the joint action space, and there is a matching exponential lower bound. This paper investigates what learning goals admit better sample complexities in the setting of $m$-player general-sum Markov games with $H$ steps, $S$ states, and $A_i$ actions per player. First, we design algorithms for learning an $\epsilon$-Coarse Correlated Equilibrium (CCE) in $\widetilde{\mathcal{O}}(H^5S\max_{i\le m} A_i / \epsilon^2)$ episodes, and an $\epsilon$-Correlated Equilibrium (CE) in $\widetilde{\mathcal{O}}(H^6S\max_{i\le m} A_i^2 / \epsilon^2)$ episodes. This is the first line of results for learning CCE and CE with sample complexities polynomial in $\max_{i\le m} A_i$. Our algorithm for learning CE integrates an adversarial bandit subroutine which minimizes a weighted swap regret, along with several novel designs in the outer loop. Second, we consider the important special case of Markov Potential Games, and design an algorithm that learns an $\epsilon$-approximate Nash equilibrium within $\widetilde{\mathcal{O}}(S\sum_{i\le m} A_i / \epsilon^3)$ episodes (when only highlighting the dependence on $S$, $A_i$, and $\epsilon$), which only depends linearly in $\sum_{i\le m} A_i$ and significantly improves over the best known algorithm in the $\epsilon$ dependence. Overall, our results shed light on what equilibria or structural assumptions on the game may enable sample-efficient learning with many players.