A central problem in the theory of multi-agent reinforcement learning (MARL)
is to understand what structural conditions and algorithmic principles lead to
sample-efficient learning guarantees, and how these considerations change as we
move from few to many agents. We study this question in a general framework for
interactive decision making with multiple agents, encompassing Markov games
with function approximation and normal-form games with bandit feedback. We
focus on equilibrium computation, in which a centralized learning algorithm
aims to compute an equilibrium by controlling multiple agents that interact
with an unknown environment. Our main contributions are:
- We provide upper and lower bounds on the optimal sample complexity for
multi-agent decision making based on a multi-agent generalization of the
Decision-Estimation Coefficient, a complexity measure introduced by Foster et
al. (2021) in the single-agent counterpart to our setting. Compared to the best
results for the single-agent setting, our bounds have additional gaps. We show
that no "reasonable" complexity measure can close these gaps, highlighting a
striking separation between single and multiple agents.
- We show that characterizing the statistical complexity for multi-agent
decision making is equivalent to characterizing the statistical complexity of
single-agent decision making, but with hidden (unobserved) rewards, a framework
that subsumes variants of the partial monitoring problem. As a consequence, we
characterize the statistical complexity for hidden-reward interactive decision
making to the best extent possible.
Building on this development, we provide several new structural results,
including 1) conditions under which the statistical complexity of multi-agent
decision making can be reduced to that of single-agent, and 2) conditions under
which the so-called curse of multiple agents can be avoided.

本文研究了多智能体强化学习中的样本效率、均衡计算和统计复杂性等问题，提出了一系列新的结构性结果，并阐述了决策时附带隐藏报酬的统计复杂度。

多智体决策的复杂性：从博弈中的学习到部分监控

On the Complexity of Multi-Agent Decision Making: From Learning in Games  to Partial Monitoring

The peculiarity of adversarial team games resides in the asymmetric
information available to the team members during the play, which makes the
equilibrium computation problem hard even with zero-sum payoffs. The algorithms
available in the literature work with implicit representations of the strategy
space and mainly resort to Linear Programming and column generation techniques
to enlarge incrementally the strategy space. Such representations prevent the
adoption of standard tools such as abstraction generation, game solving, and
subgame solving, which demonstrated to be crucial when solving huge, real-world
two-player zero-sum games. Differently from these works, we answer the question
of whether there is any suitable game representation enabling the adoption of
those tools. In particular, our algorithms convert a sequential team game with
adversaries to a classical two-player zero-sum game. In this converted game,
the team is transformed into a single coordinator player who only knows
information common to the whole team and prescribes to the players an action
for any possible private state. Interestingly, we show that our game is more
expressive than the original extensive-form game as any state/action
abstraction of the extensive-form game can be captured by our representation,
while the reverse does not hold. Due to the NP-hard nature of the problem, the
resulting Public Team game may be exponentially larger than the original one.
To limit this explosion, we provide three algorithms, each returning an
information-lossless abstraction that dramatically reduces the size of the
tree. These abstractions can be produced without generating the original game
tree. Finally, we show the effectiveness of the proposed approach by presenting
experimental results on Kuhn and Leduc Poker games, obtained by applying
state-of-art algorithms for two-player zero-sum games on the converted games

通过将序列团队游戏转化为经典二人零和游戏，并提供三种信息不损失抽象，本文有效地应用了现有算法于互弈博弈中。

对抗性团队游戏的公共信息表示

Public Information Representation for Adversarial Team Games

Algorithms for equilibrium computation generally make no attempt to ensure
that the computed strategies are understandable by humans. For instance the
strategies for the strongest poker agents are represented as massive binary
files. In many situations, we would like to compute strategies that can
actually be implemented by humans, who may have computational limitations and
may only be able to remember a small number of features or components of the
strategies that have been computed. We study poker games where private
information distributions can be arbitrary. We create a large training set of
game instances and solutions, by randomly selecting the information
probabilities, and present algorithms that learn from the training instances in
order to perform well in games with unseen information distributions. We are
able to conclude several new fundamental rules about poker strategy that can be
easily implemented by humans.

研究了通过算法学习计算尽可能易于人类实现的扑克策略，并得出了几条基本规则。

计算人类可理解策略

Computing Human-Understandable Strategies

We study the equilibrium computation problem for two classical resource
allocation games: atomic splittable congestion games and multimarket Cournot
oligopolies. For atomic splittable congestion games with singleton strategies
and player-specific affine cost functions, we devise the first polynomial time
algorithm computing a pure Nash equilibrium. Our algorithm is combinatorial and
computes the exact equilibrium assuming rational input. The idea is to compute
an equilibrium for an associated integrally-splittable singleton congestion
game in which the players can only split their demands in integral multiples of
a common packet size. While integral games have been considered in the
literature before, no polynomial time algorithm computing an equilibrium was
known. Also for this class, we devise the first polynomial time algorithm and
use it as a building block for our main algorithm.
We then develop a polynomial time computable transformation mapping a
multimarket Cournot competition game with firm-specific affine price functions
and quadratic costs to an associated atomic splittable congestion game as
described above. The transformation preserves equilibria in either games and,
thus, leads -- via our first algorithm -- to a polynomial time algorithm
computing Cournot equilibria. Finally, our analysis for integrally-splittable
games implies new bounds on the difference between real and integral Cournot
equilibria. The bounds can be seen as a generalization of the recent bounds for
single market oligopolies obtained by Todd [2016].

本文研究了两类经典资源分配博弈的均衡计算问题，提出了一种多项式时间算法来计算这些博弈的纯纳什均衡，并应用于考察单一市场的 Cournot 均衡问题。

资源分配博弈中的均衡计算

Equilibrium Computation in Resource Allocation Games

The security game is a basic model for resource allocation in adversarial
environments. Here there are two players, a defender and an attacker. The
defender wants to allocate her limited resources to defend critical targets and
the attacker seeks his most favorable target to attack. In the past decade,
there has been a surge of research interest in analyzing and solving security
games that are motivated by applications from various domains. This paper
examines security games from a theoretical perspective and provides a unified
view of various security game models. In particular, each security game can be
characterized by a set system $E$ which consists of the defender's pure
strategies, The defender's best response problem can be viewed as a
combinatorial optimization problem over $E$. Our framework captures most of the
basic security game models in the literature, including all the deployed
systems, The set system $E$ arising from various domains encodes standard
combinatorial problems like bipartite matching, maximum coverage, min-cost
flow, packing problems, etc. Our main result shows that equilibrium computation
in security games is essentially a combinatorial problem. In particular, we
prove that, for any set system $E$, the following problems can be reduced to
each other in polynomial time: (0) combinatorial optimization over $E$, (1)
computing the minimax equilibrium for zero-sum security games over $E$, (2)
computing the strong Stackelberg equilibrium for security games over $E$, (3)
computing the best or worst (for the defender) Nash equilibrium for security
games over $E$. Here, by "games over $E$" we mean the class of security games
with arbitrary payoff structures, but a fixed set $E$ of defender pure
strategies. This shows that the complexity of a security game is essentially
determined by the set system $E$.

该论文从理论的角度考虑了安全博弈，并提供了各种安全博弈模型的统一视角。研究发现，安全博弈的复杂性在本质上由集合系统 E 确定。

安全博弈之谜：平衡计算成为组合算法设计

The Mysteries of Security Games: Equilibrium Computation Becomes  Combinatorial Algorithm Design

Imperfect-recall abstraction has emerged as the leading paradigm for
practical large-scale equilibrium computation in incomplete-information games.
However, imperfect-recall abstractions are poorly understood, and only weak
algorithm-specific guarantees on solution quality are known. In this paper, we
show the first general, algorithm-agnostic, solution quality guarantees for
Nash equilibria and approximate self-trembling equilibria computed in
imperfect-recall abstractions, when implemented in the original
(perfect-recall) game. Our results are for a class of games that generalizes
the only previously known class of imperfect-recall abstractions where any
results had been obtained. Further, our analysis is tighter in two ways, each
of which can lead to an exponential reduction in the solution quality error
bound.
We then show that for extensive-form games that satisfy certain properties,
the problem of computing a bound-minimizing abstraction for a single level of
the game reduces to a clustering problem, where the increase in our bound is
the distance function. This reduction leads to the first imperfect-recall
abstraction algorithm with solution quality bounds. We proceed to show a divide
in the class of abstraction problems. If payoffs are at the same scale at all
information sets considered for abstraction, the input forms a metric space.
Conversely, if this condition is not satisfied, we show that the input does not
form a metric space. Finally, we use these results to experimentally
investigate the quality of our bound for single-level abstraction.

本文介绍了一种针对不完备信息博弈的先前未被充分理解的模型（不完全回忆抽象）的解决方案和解决质量保证方法，并提出了一种抽象算法，以求得单层游戏的最小边界。