# (A Partial Survey of) Decentralized, Cooperative
Multi-Agent Reinforcement Learning

Christopher Amato, Northeastern University

Multi-agent reinforcement learning (MARL) has exploded in popularity in recent
years. Many approaches have been developed but they can be divided into three
main types: centralized training and execution (CTE), centralized training for
decentralized execution (CTDE), and Decentralized training and execution
(DTE).

CTE methods assume centralization during training and execution (e.g., with
fast, free and perfect communication) and have the most information during
execution. That is, the actions of each agent can depend on the information
from all agents. As a result, a simple form of CTE can be achieved by using a
single-agent RL method with the centralized action and observation spaces
(maintaining a centralized action-observation history for the partially
observable case). CTE methods can potentially outperform the decentralized
execution methods (since they allow centralized control) but are less scalable
as the (centralized) action and observation spaces can scale exponentially
with the number of agents. CTE is typically only used in the cooperative MARL
case since centralized control implies cooperation. CTDE methods are perhaps
the most common as they can use centralized information during training but
execute in a decentralized manner—using only information available to that
agent during execution. As a result, they can be more scalable than CTE
methods, do not require communication during execution, and can often perform
well. CTDE fits most naturally with the cooperative case, but can be
potentially applied in competitive or mixed settings depending on what
information is assumed to be observed. Decentralized training and execution
methods make the fewest assumptions and are often simple to implement. In
fact, as I’ll discuss, any single-agent RL method can be used for DTE by just
letting each agent learn separately. Of course, there are pros and cons to
such approaches as we discuss below. It is worth noting that DTE is required
if no offline coordination is available. That is, if all agents must learn
during online interactions without prior coordination, learning and execution
must both be decentralized. DTE methods can be applied in cooperative,
competitive, or mixed cases but this text will focus on the cooperative MARL
case.

MARL methods can be further broken up into value-based and policy gradient
methods. Value-based methods (e.g., Q-learning) learn a value function and
then choose actions based on those values. Policy gradient methods learn an
explicit policy representation and attempt to improve the policy in the
direction of the gradient. Both classes of methods are widely used in MARL.

In this text, I will first give a brief description of the cooperative MARL
problem in the form of the Dec-POMDP. Then, I will discuss value-based DTE
methods starting with independent Q-learning and its extensions and then
discuss the extension to the deep case with DQN, the additional complications
this causes, and methods that have been developed to (attempt to) address
these issues. Next, I will discuss policy gradient DTE methods starting with
independent REINFORCE (i.e., vanilla policy gradient), and then extending to
the actor-critic case and deep variants (such as independent PPO). Finally, I
will discuss some general topics related to DTE and future directions.

The basics of reinforcement learning (in the single-agent setting) are not
presented in this text. Anyone interested in RL should read the book by Sutton
and Barto (2018). Similarly, for a broader overview of MARL, the recent book
by Albrecht, Christianos and Schäfer is recommended (Albrecht et al., 2024).

It is worth noting that this survey is partial in two respects. First, it is
from my viewpoint. Second, it does not cover all work in decentralized,
cooperative MARL. This subarea has less work than subareas such as CTDE but it
is still more extensive than presented here. I have included work that I
believe is important for understanding the main concepts in the subarea and
apologize for those that I have omitted.

##  1 The cooperative MARL problem: The Dec-POMDP

Figure 1: A depiction of cooperative MARL—a Dec-POMDP.

The cooperative multi-agent reinforcement learning (MARL) problem can be
represented as a Dec-POMDP (Oliehoek and Amato, 2016; Bernstein et al., 2002).
Dec-POMDPs generalize POMDPs (Kaelbling et al., 1998) (and MDPs (Puterman,
1994)) to the multi-agent, decentralized setting. As depicted in Figure 1,
multiple agents operate under uncertainty based on partial views of the world,
with execution unfolding over time. At each step, every agent chooses an
action (in parallel) based purely on locally observable information, resulting
in each agent obtaining an observation and the team obtaining a joint reward.
The shared reward function makes the problem cooperative, but their local
views mean that execution is decentralized.

Formally, a Dec-POMDP is defined by tuple
$\langle\mathbb{I},\mathbb{S},\\{{\mathbb{A}}_{i}\\},T,R,\\{{\mathbb{O}}_{i}\\},O,\mathcal{H},\gamma\rangle$,
where

  * •

$\mathbb{I}$ is a finite set of agents;

  * •

$\mathbb{S}$ is a set of states with designated initial state distribution
${{{b}}_{0}}$;

  * •

${\mathbb{A}}_{i}$ is a set of actions for each agent $i$ with
$\mathbf{\mathbb{A}}=\times_{i}{\mathbb{A}}_{i}$ the set of joint actions;

  * •

$T$ is a state transition probability function,
$T:\mathbb{S}\times\mathbf{\mathbb{A}}\times\mathbb{S}\to[0,1]$, that
specifies the probability of transitioning from state $s\in\mathbb{S}$ to
$s^{\prime}\in\mathbb{S}$ when the actions $\mathbf{a}\in\mathbf{\mathbb{A}}$
are taken by the agents (i.e.,
$T(s,\mathbf{a},s^{\prime})=\Pr(s^{\prime}|\mathbf{a},s)$);

  * •

$R$ is a reward function:
$R:\mathbb{S}\times\mathbf{\mathbb{A}}\to\mathbb{R}$, the immediate reward for
being in state $s\in\mathbb{S}$ and taking the actions
$\mathbf{a}\in\mathbf{\mathbb{A}}$;

  * •

${\mathbb{O}}_{i}$ is a set of observations for each agent, $i$, with
$\mathbf{\mathbb{O}}=\times_{i}{\mathbb{O}}_{i}$ the set of joint
observations;

  * •

$O$ is an observation probability function:
$O:\mathbf{\mathbb{O}}\times\mathbf{\mathbb{A}}\times\mathbb{S}\to[0,1]$, the
probability of seeing observations $\mathbf{o}\in\mathbf{\mathbb{O}}$ given
actions $\mathbf{a}\in\mathbf{\mathbb{A}}$ were taken and resulting in state
$s^{\prime}\in\mathbb{S}$ (i.e.,
$O(\mathbf{a},s^{\prime},\mathbf{o})=\Pr(\mathbf{o}|\mathbf{a},s^{\prime})$);

  * •

$\mathcal{H}$ is the number of steps until termination, called the horizon;

  * •

and $\gamma\in[0,1]$ is the discount factor.

A solution to a Dec-POMDP is a _joint policy_ , denoted $\mathbf{\pi}$—a set
of policies, one for each agent, each of which is denoted ${\pi}_{i}$. Because
the state is not directly observed, it is typically beneficial for each agent
to remember a history of its observations. Then, a _local policy_ ,
${\pi}_{i}$, for an agent is a mapping from local action-observation histories
to actions, ${\mathbb{H}}_{i}\to{\mathbb{A}}_{i}$, where ${\mathbb{H}}_{i}$ is
the set of local observation histories,
${h}_{i}=\\{{a}_{i,1},{o}_{i,1},\ldots,{a}_{i,t},{o}_{i,t}\\}$111Sometimes,
${o}_{i,0}$ is also included as an observation generated by the initial state
distribution., by agent $i$ up to the current time step, $t$. Many researchers
just use observation histories (without including actions), which is
sufficient for deterministic policies but may not be for stochastic policies
(Oliehoek and Amato, 2016). Note that histories have implicit time steps due
to their length which we do not include in the notation (i.e., we always
assume a history starts on the first time step and the last time step is
defined by the number of action-observation pairs). We can denote the
histories for all agents at a given time step as
$\mathbf{h}{}=\langle{h}_{1},\ldots,{h}_{n}\rangle$. Because one policy is
generated for each agent and these policies depend only on local observations,
they operate in a decentralized manner.

While there always exists an optimal deterministic joint policy in Dec-POMDPs,
we can also use stochastic joint policies, overloading notation with:
$\mathbf{\pi}(\mathbf{a}|\mathbf{h}{})=\prod_{i\in\mathbb{I}}{\pi}_{i}({a}_{i}|{h}_{i})$,
where ${\pi}_{i}({a}_{i}|{h}_{i})$ represents the local policy for agent $i$
and the probability of choosing action ${a}_{i}$ in history ${h}_{i}$.
Deterministic policies will be used in the value-based methods in Section 2
while stochastic policies will be used in the policy gradient gradient methods
in Section 3.

The value of a joint policy, $\pi$, at joint history $\mathbf{h}{}$ can be
defined for the case of discrete states and observations as

$V^{\mathbf{\pi}}(\mathbf{h}{})=\sum_{s}P(s|\mathbf{h}{},{{{b}}_{0}})\Big{[}R(s,\mathbf{\pi}(\mathbf{h}{}))+\gamma\sum_{s^{\prime}}P(s^{\prime}|\mathbf{\pi}(\mathbf{h}{}),s)\sum_{\mathbf{o}}P(\mathbf{o}|\mathbf{\pi}(\mathbf{h}{}),s^{\prime})V^{\mathbf{\pi}}(\mathbf{h}{}\mathbf{\pi}(\mathbf{h}{})\mathbf{o})\Big{]}$

where $P(s|\mathbf{h}{},{{{b}}_{0}})$ is the probability of state $s$ after
observing joint history $\mathbf{h}{}$ starting from state distribution
${{{b}}_{0}}$ and $\mathbf{\pi}(\mathbf{h}{})$ is the joint action taken at
the joint history. Also, $\mathbf{h}{}\mathbf{\pi}(\mathbf{h}{})\mathbf{o}$
represents $\mathbf{h}{}^{\prime}$, the joint history after taking joint
action $\mathbf{\pi}(\mathbf{h}{})$ in joint history $\mathbf{h}{}$ and
observing joint observation $\mathbf{o}$. In the RL context, algorithms do not
iterate over states and observations to explicitly calculate this expectation
but approximate it through sampling. For the finite-horizon case,
$V^{\mathbf{\pi}}(\mathbf{h}{})=0$ when the length of $\mathbf{h}{}$ equals
the horizon $\mathcal{H}$, showing the value function includes the time step
from the history. The discount factor, $\gamma$, is typically set to 1 in the
finite-horizon case and $\gamma\in[0,1)$ in the infinite-horizon case
($\mathcal{H}=\infty$)222The episodic case (Sutton and Barto, 2018) is
typically indefinite-horizon with termination to a set of terminal states with
probability 1 and the infinite-horizon case is sometimes called ‘continuing.’.

We will also evaluate policies starting from the initial, null history as
$V^{\mathbf{\pi}}(\mathbf{h}{}_{0})$. An _optimal joint policy_ beginning at
$\mathbf{h}{}_{0}$ is
$\mathbf{\pi}^{*}(\mathbf{h}{}_{0})=\operatorname*{arg\,\\!max}_{\mathbf{\pi}}V^{\mathbf{\pi}}(\mathbf{h}{}_{0})$.
That is, the optimal joint policy is the set of local policies for each agent
that provides the highest value, which is denoted $V^{*}$.

Reinforcement learning methods often use history-action values,
$Q(\mathbf{h}{},\mathbf{a})$, rather than just history values
$V(\mathbf{h}{})$. $Q^{\mathbf{\pi}}(\mathbf{h}{},\mathbf{a})$ is the value of
choosing joint action $\mathbf{a}$ at joint history $\mathbf{h}{}$ and then
continuing with policy $\mathbf{\pi}$,

$Q^{\mathbf{\pi}}(\mathbf{h}{},\mathbf{a})=\sum_{s}P(s|\mathbf{h}{},{{{b}}_{0}})\Big{[}R(\mathbf{a},s)+\gamma\sum_{s^{\prime}}P(s^{\prime}|\mathbf{a},s)\sum_{\mathbf{o}}P(\mathbf{o}|\mathbf{a},s^{\prime})Q^{\mathbf{\pi}}\big{(}\mathbf{h}{}\mathbf{a}\mathbf{o},\mathbf{\pi}(\mathbf{h}{}\mathbf{a}\mathbf{o})\big{)}\Big{]},$

while $Q^{*}(\mathbf{h}{},\mathbf{a})$ is the value of choosing action
$\mathbf{a}$ at history $\mathbf{h}{}$ and then continuing with the optimal
policy, $\mathbf{\pi}^{*}$.

##### Policies that depend only on a single observation

It is somewhat popular to define policies that depend only on a single
observation rather than the whole observation history. That is,
${\pi}_{i}:{\mathbb{O}}_{i}\to{\mathbb{A}}_{i}$, rather than
${\mathbb{H}}_{i}\to{\mathbb{A}}_{i}$. This type of policy is ofter referred
to as _reactive_ or _Markov_ since it just depends on (or reacts from) the
past observation. These reactive policies are typically not desirable since
they can be arbitrarily worse than policies that consider history information
(Murphy, 2000) but can perform well or even be optimal in simpler subclasses
of Dec-POMDPs (Goldman and Zilberstein, 2004). In general, reactive policies
reduce the complexity of finding a solution (since many fewer policies need to
be considered) but only perform well when the problem is not really partially
observable.

##  2 Decentralized, value-based methods

Value-based methods (such as Q-learning (Watkins and Dayan, 1992)) learn a
value function and the policy is implicitly defined based on those values
(i.e., choosing the action that maximizes the value function). Some of the
earliest MARL methods are based on applying Q-learning to each agent. For
instance, Claus and Boutilier (1998) decompose MARL approaches into
_independent learners_ (IL) and _joint-action learners_ (JAL). ILs learn
Q-functions that depend on their own information (ignoring other agents) while
JALs learn joint Q-functions, which include the actions of the other agents.
These concepts were originally defined for the fully observable, bandit (i.e.,
stateless) case but can be extended to the partially observable, stateful
case. For example, we can define an IL Q-function as $Q_{i}({h}_{i},{a}_{i})$,
which provides a value for agent $i$’s history ${h}_{i}$ and action ${a}_{i}$.
A JAL Q-function $Q_{i}(\mathbf{h}{},\mathbf{a})$ for agent $i$ would depend
on the joint information $\mathbf{h}{}$ and $\mathbf{a}$. All decentralized
value-based MARL methods are ILs since they never have access to the joint
information, $\mathbf{h}{}$ and $\mathbf{a}$.

In particular decentralized value-based MARL methods for Dec-POMDPs:

  * •

assume at each step, each agent, $i$, observes the action it took, ${a}_{i}$,
its resulting observation, ${o}_{i}$, as well as the joint reward, $r$, and

  * •

estimate a value function based solely on this information (i.e., episodes
consisting of sequences of ${a}_{i},{o}_{i},r$).

As a result, as we will discuss, any (partially observable) single-agent MARL
method can be a DTE MARL method by ignoring the fact that other agents exist
and learning as if they were the only agent in the problem. Such methods may
have issues with convergence and performance (as we’ll discuss below) but this
is exactly what is done by our first approach: Independent Q-learning.

###  2.1 Independent Q-learning (IQL)

IQL just applies Q-learning to each agent independently. That is, each agent
learns its own local Q-function, $Q_{i}$, using Q-learning on its own data.
Pseudocode for a version of IQL for the Dec-POMDP case is provided in
Algorithm 1. Just like Q-learning in the single-agent case, that algorithm
uses a learning rate, $\alpha$, and some form of exploration, which in this
case is $\epsilon$-greedy. Each agent initializes their Q-function (e.g., to
0, optimistically, etc.), and then iterates over episodes (either a fixed set
or until convergence). During each episode, the agent chooses an action with
exploration, sees the joint reward and its own observation and then updates
the Q-value at the current history, ${h}_{i}$, given the current Q-estimates
and the reward using the standard Q-learning update (line 9). The history is
updated by appending the action taken and observation seen to the current
history and the episode continues until the horizon is reached.

Note that the Q-functions are inherently timed as the history length defines
the current time step, making the algorithm fit with the finite-horizon case.
Regardless, the algorithm can easily be extended to the episodic/indefinite-
horizon case by including terminal states (or histories) instead of a fixed
horizon.

1: set $\alpha$ and $\epsilon$

2: Initialize ${Q}_{i}$ for all
${h}_{i}\in{\mathbb{H}}_{i},{a}_{i}\in{\mathbb{A}}_{i}$

3: for all episodes do

4: ${h}_{i}\leftarrow\emptyset$ {Empty initial history}

5: for $t=1$ to $\mathcal{H}$ do

6: Choose ${a}_{i}$ at ${h}_{i}$ from ${Q}_{i}({h}_{i},\cdot)$ with
exploration (e.g., $\epsilon$-greedy)

7: See joint reward $r$, local observation ${o}_{i}${Depends on joint action
$\mathbf{a}$}

8: ${h}_{i}^{\prime}\leftarrow{h}_{i}{a}_{i}{o}_{i}$

9:
${Q}_{i}({h}_{i},{a}_{i})\leftarrow{Q}_{i}({h}_{i},{a}_{i})+\alpha\left[r+\gamma\max_{{a}_{i}^{\prime}}{Q}_{i}({h}_{i}^{\prime},{a}_{i}^{\prime})-{Q}_{i}({h}_{i},{a}_{i})\right]$

10: ${h}_{i}\leftarrow{h}_{i}^{\prime}$

11: end for

12: end for

13: return ${Q}_{i}$

Algorithm 1 Independent Q-Learning for agent $i$ (finite-horizon)

##### Important hidden information

This algorithm runs in the underlying Dec-POMDP but the details of those
dynamics in the environment are not shown (as they are not visible to the
agent). For example, at the beginning of each episode, the state, $s$, is
sampled from the initial state distribution ${{{b}}_{0}}$, and when agents
take joint action $\mathbf{a}$ the reward is generated from the reward
function, $R(s,\mathbf{a})$, the next state $s^{\prime}$ is sampled from the
transition dynamics with probability $\Pr(s^{\prime}|s,\mathbf{a})$, and the
joint observation is sampled from the observation function
$\Pr(\mathbf{o}|s^{\prime},\mathbf{a})$. This process continues until the end
of the episode.

While independent Q-learning ignores the other agents, it still depends on
them in order to generate the joint reward $r$ and the local observation
$o_{i}$ since both of these depend on the actions of all agents. That is, from
agent $i$’s perspective, it is learning in a (single-agent) POMDP, as
Algorithm 1 shows (the states of the POMDP would be the states of the Dec-
POMDP plus the histories of the other agents).333 The idea of fixing other
agent policies and then solving the resulting POMDP (either by planning
methods (Nair et al., 2003) or RL methods (Banerjee et al., 2012)) has had
success and results in a best response for agent $i$. Furthermore, iterating
over agents, $i$, fixing other agent policies, $\neg i$, and calculating best
responses will lead to a local optimum of the Dec-POMDP (Banerjee et al.,
2012). Unfortunately, such methods require coordination to communicate which
agent’s turn it is to learn so they are not appropriate for the DTE case.

In particular, as pointed out in previous papers (Lauer and Riedmiller,
2000)444Note the paper considers the fully observable deterministic transition
case but we extend the idea to the Dec-POMDP case., independent Q-learning is
actually learning a Q-function for each agent based on the actions selected by
the other agents during training. That is, agent $i$ would use data that
depends on the actions taken by the other agents (and observations other
agents see) even if it doesn’t directly observe those actions (and
observations). In the partially observable case, the following Q-function
would be learned:

$Q_{i}({h}_{i},{a}_{i})=\sum_{\mathbf{a}\in\mathbf{\mathbb{A}}}\hat{P}(\mathbf{a},\mathbf{h}{}|{h}_{i},{a}_{i})\left[r+\gamma\sum_{{o}_{i}}\hat{P}({o}_{i}|\mathbf{h}{},\mathbf{a})\max_{{a}_{i}^{\prime}}Q_{i}({h}_{i}^{\prime},{a}_{i}^{\prime})\right]$
(1)

where $P(\mathbf{a},\mathbf{h}{}|{h}_{i},{a}_{i})$ is the empirical
probability that the joint action $\mathbf{a}$ and joint history
$\mathbf{h}{}$ occurs when agent $i$ selects its action ${a}_{i}$ in
${h}_{i}$. This is precisely when independent Q-learning will update
$Q_{i}({h}_{i},{a}_{i})$ and it will use the joint reward $r$ and agent’s
observation function $P({o}_{i}^{\prime}|\mathbf{a},\mathbf{h}{})$, which
approximates
$P({o}_{i}^{\prime}|\mathbf{a},s^{\prime})P(s^{\prime}|\mathbf{a},s)$, where
$P({o}_{i}^{\prime}|\mathbf{a},s^{\prime})$ marginalizes out other agent
observations from the joint function
$P(\mathbf{o}^{\prime}|\mathbf{a},s^{\prime})$.
$\hat{P}({o}_{i}|\mathbf{h}{},\mathbf{a})$ is the empirical probability based
on observing ${o}_{i}$ from $\mathbf{h}{}$ after taking action $\mathbf{a}$.
Therefore, IQL is assuming the other agents are part of the environment and
learning a Q-function for the resulting POMDP. If the other agents are not
learning and do in fact have fixed policies, the problem would just reduce to
this POMDP. Unfortunately, the other agents would also typically be learning,
leading to nonstationarity in the underlying POMDP and difficulty with
coordinated action selection.

##### Convergence and solutions

In the case of IQL, the underlying POMDP that is being learned is non-
stationary since the other agents are also learning and thus changing their
policies over time. This may cause IQL to not converge (Tan, 1993).
Convergence of Q-learning in the multi-agent case is an active area of
research (Claus and Boutilier, 1998; Tuyls et al., 2003; Wunder et al., 2010;
Hussain et al., 2023), it is still an open question what assumptions will
allow convergence and to what (unlike the policy gradient case where
convergence to a local optimum is assured under mild assumptions (Peshkin et
al., 2000; Lyu et al., 2023))555In fact, while Q-learning can provably
converge to a global optimum in the single-agent case (Jaakkola et al., 1993),
there are no known MARL algorithms that have guaranteed convergence to a
global optimum. This is an interesting area for future research!.

It is worth pointing out that even if algorithms can converge to an optimal
Q-value (or any Q-value), agents may not be able to select optimal actions if
there are multiple optimal policies (Lauer and Riedmiller, 2000). In this
case, agents would need to coordinate on their actions to make sure they
choose actions from the same joint policy but this is not possible with only
individual Q-values (e.g., if
${Q}_{1}({h}_{1},{a}_{1}^{1})=Q_{1}({h}_{1},{a}_{1}^{2})$ and
${Q}_{2}({h}_{2},{a}_{2}^{1})={Q}_{2}({h}_{2},{a}_{2}^{2})$ but
$Q({h}_{1},{h}_{2},{a}_{1}^{1},{a}_{2}^{2})=Q({h}_{1},{h}_{2},{a}_{1}^{2},{a}_{2}^{1})<Q({h}_{1},{h}_{2},{a}_{1}^{2},{a}_{2}^{2})=Q({h}_{1},{h}_{2},{a}_{1}^{1},{a}_{2}^{1})$—agents
must take the same actions to be optimal).

IQL is very simple but can perform well (Tan, 1993; Sen et al., 1994; Tampuu
et al., 2017). It is also the basis for the other value-based DTE MARL
methods.

###  2.2 Improving the performance of IQL

Several extensions of IQL have been developed to improve performance and
better fit with the MARL setting. While the below algorithms were developed
for the fully observable case (the multi-agent MDP (Oliehoek and Amato,
2016)), we extend them to the partially observable case here to fit better
with our Dec-POMDP setting.

####  2.2.1 Distributed Q-learning

In order to promote coordination, Distributed Q-learning (Lauer and
Riedmiller, 2000) makes strong optimistic assumptions. In particular,
extending to the partially observable case, it uses the following Q-update:

$Q_{i}({h}_{i},{a}_{i})=\max\left\\{Q_{i}({h}_{i},{a}_{i}),r+\gamma\max_{{a}_{i}^{\prime}}Q_{i}({h}_{i}^{\prime},{a}_{i}^{\prime})\right\\}$
(2)

where the current Q-value is kept if it is higher than (or equal to) the new
estimate
$r+\gamma\max_{{a}_{i}^{\prime}}Q_{i}({h}_{i}^{\prime},{a}_{i}^{\prime})$.
Otherwise, the Q-value is updated to be the new estimate. The intuition behind
this optimistic update is that other agents will make mistakes during training
because they have suboptimal policies or because they are exploring. Agents
don’t necessarily want to learn from these mistakes. Instead, agents want to
learn from the best policies of the other agents such as those that choose
actions that generate high-reward values, even if they don’t happen very
often. In the special case of deterministic MMDPs (the multi-agent fully
observable case, see Oliehoek and Amato (2016)), this approach will learn the
same Q-function as centralized Q-learning (which will converge to the optimal
Q-values in the limit). This is unlike IQL which can get stuck in local optima
or never converge at all.

Because Distributed Q-learning learns individual Q-values, agents may still
not be able to select optimal actions due to the coordination issue mentioned
above. As a result, Distributed Q-learning stores the current best policy for
each agent (i.e., if the Q-value is updated, the action that resulted in that
update is stored for that state in the fully observable case or history in the
partially observable case). Including this coordination mechanism, the
algorithm can converge to optimal Q-functions and optimal policies in the
limit for the fully observable deterministic case.

In the more general stochastic case, distributed Q-learning is not able to
distinguish between environmental stochasticity and agent stochasticity. That
is, if getting a high-valued reward is unlikely (due to reward or transition
stochasticity) distributed Q-learning will assume it can be gotten with
probability one using max rather than taking the expectation (over other agent
policies and stochastic transitions) as in Equation 1. As a result,
distributed Q-learning is overly optimistic in the stochastic case and may
perform poorly. Learning and incorporating the probabilities in Equation 1 and
then calculating the expectation over the next step Q-value could fix this
problem but would assume agents observe the actions of other agents which is
not the case for decentralized training.

####  2.2.2 Hysteretic Q-learning

To maintain the idea of optimism while accounting for stochasticity,
hysteretic Q-learning (Matignon et al., 2007) was developed. The idea is to
use two learning rates, $\alpha$ and $\beta$ with $\alpha>\beta$. That is,
agents update their Q-values more during a positive experience than a negative
one.

In particular, if we define the TD error as:

$\delta\leftarrow
r+\gamma\max_{a_{i}^{\prime}}Q({h}_{i}^{\prime},a_{i}^{\prime})-Q_{i}({h}_{i},{a}_{i}),\\\
$

then we can rewrite distributed Q-learning (using a learning rate $\alpha$)
as:

$Q_{i}({h}_{i},{a}_{i})=\begin{cases}Q_{i}({h}_{i},{a}_{i})+\alpha\delta\quad\text{if}\quad\delta>0\\\
Q_{i}({h}_{i},{a}_{i})\quad\text{else}\end{cases}$ (3)

highlighting the fact that positive experiences (in terms of TD error) cause
updates to the Q-function while negative ones do not.

Hysteretic Q-learning, in contrast, adds the second learning rate $\beta$ to
the negative experiences:

$Q_{i}({h}_{i},{a}_{i})=\begin{cases}Q_{i}({h}_{i},{a}_{i})+\alpha\delta\quad\text{if}\quad\delta>0\\\
Q_{i}({h}_{i},{a}_{i})+\beta\delta\quad\text{else}\end{cases}$ (4)

This ensures learning still occurs in the negative cases but the update is
less than in the positive cases because $\alpha>\beta$. Therefore, hysteretic
Q-learning is still optimistic (hoping the positive experiences are because of
better action choices and not stochasticity) but is less optimistic than
distributed Q-learning. The implementation is also very simple (although it
does require tuning two learning rates). Hysteretic Q-learning is very simple
but can perform well in a range of domains (Matignon et al., 2007). Also, note
that as $\beta$ approaches $\alpha$, hysteretic Q-learning will become
standard Q-learning and as $\beta$ approaches 0, it will become distributed
Q-learning.

####  2.2.3 Lenient Q-learning

While it is possible to decay $\beta$ towards $\alpha$ as learning continues,
to be more optimistic at the beginning of learning (when a lot of exploration
is happening) and still be robust to stochasticity as learning converges,
lenient Q-learning (Wei and Luke, 2016) allows agents to adjust this
_leniency_ towards exploration on a history-action pair basis. Specifically,
lenient Q-learning maintains a temperature, $T({h}_{i},{a}_{i})$, per history-
action pair that adjusts the probability that a negative update at a
particular history-action pair will be ignored. These temperature values allow
history-action pairs that have not been visited often to not be updated yet,
while frequently visited history-action pairs are updated as in IQL.

The lenient Q-learning update is:

${Q}_{i}({h}_{i},{a}_{i})=\begin{cases}{Q}_{i}({h}_{i},{a}_{i})+\alpha\delta\quad\text{if}\quad\delta>0\quad\text{or}\quad
rand\sim U(0,1)>1-e^{-K*T({h}_{i},{a}_{i})}\\\
{Q}_{i}({h}_{i},{a}_{i})\quad\quad\quad\text{else}\end{cases}$ (5)

$T({h}_{i},{a}_{i})$ is initialized to a maximum temperature, and is decayed
after an update with
$T({h}_{i},{a}_{i})~{}\leftarrow~{}\lambda T({h}_{i},{a}_{i})$ for
$\lambda\in(0,1)$ and leniency parameter $K$ adjusts the impact of the
temperature on the probability distribution. The resulting Q-update will
probabilistically update Q based on how often history-action pairs are
visited, with more frequently visited pairs being more likely to be updated
when the TD error is negative.

Lenient Q-learning can outperform hysteretic Q-learning since it can adjust
the amount of optimism in a more fine-grained way but it also requires
maintaining (and updating) temperature values as well as Q-values. Maintaining
these values can be more problematic in the partially observable case since
the history-action space grows exponentially with the problem horizon (or
history length more generally).

###  2.3 Deep extensions, issues, and fixes

In order to scale to larger domains, deep extensions of the above algorithms
have been developed. These approaches are typically based on deep Q-networks
(DQN) (Mnih et al., 2015). While DQN can scale to larger action and
observation spaces, the decentralized multi-agent context can cause problems.
We first discuss the basics of DQN and its extension to the partially
observable case, D _R_ QN, and then discuss a deep version of IQL, independent
DRQN (Tampuu et al., 2017), the coordination issues with the approach, and
some proposed fixes.

####  2.3.1 DQN and DRQN

Deep Q-networks (DQN) (Mnih et al., 2015) is an extension of Q-learning
(Watkins and Dayan, 1992) to include a neural net as a function approximator.
That is, DQN learns $Q_{\theta}(s,a)$, parameterized with $\theta$ (i.e.,
$\theta$ represents the parameters of the neural network), by minimizing the
loss:

$\mathcal{L}(\theta)=\mathbb{E}_{<s,a,r,s^{\prime}>\sim\mathcal{D}}\Big{[}\big{(}y-Q_{\theta}(s,a)\big{)}^{2}\Big{]}\text{,
where\,\, }y=r+\gamma\max_{a^{\prime}}Q_{\theta^{-}}(s^{\prime},a^{\prime})$
(6)

which is just the squared TD error—the difference between the current
estimated value, $Q_{\theta}(s,a)$, and the new value gotten from adding the
newly seen reward to the previous Q-estimate at the next state,
$Q_{\theta^{-}}(s^{\prime},a^{\prime})$. Because learning neural networks can
be unstable, a separate target action-value function, $Q_{\theta^{-}}$, and an
experience replay buffer $\mathcal{D}$ (Lin, 1992) are implemented to
stabilize learning. The target network is an older version of the Q-estimator
that is updated periodically, the experience replay buffer stores
$s,a,s^{\prime},r$ sequences and single $s,a,s^{\prime},r$ tuples are i.i.d.
sampled for updates. As shown in Figure 2(a), the neural network (NN) outputs
values for all actions ($a\in\mathbb{A}$) to make maxing at a state possible
with a single forward pass (rather than iterating through the actions).

Deep recurrent Q-networks (DRQN) (Hausknecht and Stone, 2015) extends DQN to
handle partial observability, where some number of recurrent layers (e.g.,
LSTM (Hochreiter and Schmidhuber, 1997)) are included to maintain an internal
hidden state which is an abstraction of the history (as shown in Figure 2(b)).
Because the problem is partially observable, $o,a,o^{\prime},r$ sequences are
stored in the replay buffer during execution. The update equation is very
similar to that of DQN:

$\mathcal{L}(\theta)=\mathbb{E}_{<h,a,r,o>\sim\mathcal{D}}\Big{[}\big{(}y-Q_{\theta}(h,a)\big{)}^{2}\Big{]}\text{,
where\,\, }y=r+\gamma\max_{a^{\prime}}Q_{\theta^{-}}(h^{\prime},a^{\prime})$
(7)

but since a recurrent neural network (RNN) is used, the internal state of the
RNN can be thought of as a history representation. That is, instead of
learning Q-functions using full histories (i.e.,
$h=o_{0},a_{1},o_{1},r_{1},\ldots,o_{t-1},a_{t},o_{t},r_{t}$), $h$ is the
internal state of the RNN after sequentially inputing the history sequence
($h=o_{0},a_{1},o_{1},\ldots,o_{t-1},a_{t},o_{t}$). Similarly,
$h^{\prime}=hao^{\prime}$, which can be thought of as the new history after
appending $o^{\prime}$ and $a$ to $h$, which is achieved by inputing $a$ and
$o^{\prime}$ to the RNN when its current state is $h$. Technically, a whole
history (e.g., episode) should be sampled from the replay buffer to train the
recurrent network but it is common to use a fixed history length (e.g., sample
$o,a,o^{\prime},r$ sequences of length 10). As mentioned above, many
implementations just use observation histories rather than full action-
observation histories. With the popularity of DRQN, it has become common to
add recurrent layers to standard (fully observable) deep reinforcement
learning methods when solving partially observable problems.

(a) DQN

(b) DRQN

(c) Independent DRQN

Figure 2: DQN, DRQN, and independent DRQN diagrams.

####  2.3.2 Independent DRQN (IDRQN)

Independent DRQN (IDRQN) (Tampuu et al., 2017)666Again, the original algorithm
only considers the fully observable case but we consider the extension to the
Dec-POMDP case. combines IQL and DRQN. As seen in Algorithm 2, the basic
structure is the same as IQL but ${Q}_{i}$ is estimated using an RNN
parameterized by $\theta$ (shown in Figure 2(c)), along with using a target
network, $\theta^{-}$, and a replay buffer, $\mathcal{D}$. First, episodes are
generated by interacting with the environment (e.g., $\epsilon$-greedy
exploration), which are added to the replay buffer. This buffer typically has
a fixed size and new data replaces old data when the buffer is full. Episodes
can then be sampled from the replay buffer (either single episodes or as a
minibatch of episodes). In order to have the correct internal state, RNNs are
trained sequentially. Training is done from the beginning of the episode until
the end777It is common in practice to use a fixed history length and sample
windows of that length rather than training with full episodes., calculating
the internal state and the loss at each step and updating $\theta$ using
gradient descent. The target network $\theta^{-}$ is updated periodically
(every $C$ episodes in the code) by copying the parameters from $\theta$.

1: set $\alpha$ and $\epsilon$

2: Initialize network parameters $\theta$ and $\theta^{-}$ for ${Q}_{i}$

3: $\mathcal{D}_{i}\leftarrow\emptyset$

4: $e\leftarrow 1$ {episode index}

5: for all episodes do

6: ${h}_{i}\leftarrow\theta^{RNN}$ {initial history is the initial RNN state
of the network}

7: for $t=1$ to $\mathcal{H}$ do

8: Choose ${a}_{i}$ at ${h}_{i}$ from ${Q}_{i}^{\theta}({h}_{i},\cdot)$ with
exploration (e.g., $\epsilon$-greedy)

9: See joint reward $r$, local observation ${o}_{i}${Depends on joint action
$\mathbf{a}$}

10: append ${a}_{i},{o}_{i},r$ to $\mathcal{D}_{i}^{e}$

11: ${h}_{i}\leftarrow{h}_{i}{a}_{i}{o}_{i}$ {update RNN state of the network}

12: end for

13: sample an episode from $\mathcal{D}$

14: for $t=1$ to $\mathcal{H}$ do

15: ${h}_{i}\leftarrow\theta^{RNN}$ {initial history is the initial RNN state
of the network}

16: ${a}_{i},{o}_{i},r\leftarrow\mathcal{D}^{e}_{i}(t)$

17: ${h}_{i}^{\prime}\leftarrow{h}_{i}{a}_{i}{o}_{i}$

18:
$y=r+\gamma\max_{{a}_{i}^{\prime}}{Q}_{i}^{\theta^{-}}({h}_{i}^{\prime},{a}_{i}^{\prime})$

19: Perform gradient descent on parameters $\theta$ with the loss:
$\big{(}y-{Q}_{i}^{\theta}({h}_{i},{a}_{i})\big{)}^{2}$

20: ${h}_{i}\leftarrow{h}_{i}^{\prime}$

21: end for

22: if $e\mod C=0$ then

23: $\theta^{-}\leftarrow\theta$

24: end if

25: $e\leftarrow e+1$

26: end for

27: return ${Q}_{i}$

Algorithm 2 Independent DRQN (IDRQN) for agent $i$ (finite-horizon*)

While the pseudocode uses a horizon, the resulting Q-functions no longer
reflect the time step based on the history since histories of different
lengths may be combined into the same representation in the RNN. As a result,
untimed/stationary Q-values are learned that just depend on the RNN internal
state, which we still call $h$, and not the time step. This stationary
representation is technically incorrect for the finite-horizon case (even
though it is widely used in practice). Again, the code can be adjusted to the
episodic/indefinite-horizon case by replacing the horizon with terminal states
or the infinite-horizon case by removing the loop over episodes (both of which
fix the issue with timed Q-functions as these cases do not require them).
Lastly, the pseudocode, for this approach and throughout the text, is written
to be simple and highlight the main algorithmic components. There are many
implementation tricks, especially in the deep case, that are not included.

##### Issues with IDRQN

Independent DRQN can perform well but has a number of issues. For example,
early methods disabled experience replay (Foerster et al., 2016)888Other
methods for improving experience replay in MARL exist, but they typically
assume the CTDE setting (such as Foerster et al. (2017)).. They found that
performance was worse with experience replay than without it. This is because
agents are no longer learning concurrently when using the replay
buffer—experience is generated from the behavior of all agents (i.e.,
concurrently) but is then put into the buffer for learning. When learning,
different agents will sample and learn from different experiences. Learning
from this different data makes performance noisy and unstable. This makes
intuitive sense since agents will update their Q-functions (and resulting
policies) based on (potentially very) different experiences. We discuss a
simple fix next.

####  2.3.3 Deep hysteretic-Q and concurrent buffer

Hysteretic Q-learning has been extended to the deep case in the form of
decentralized hysteretic deep recurrent Q-networks (Dec-HDRQN) (Omidshafiei et
al., 2017). Dec-HDRQN makes two main contributions: the use of hysteresis with
D(R)QN, and a concurrent replay buffer to improve performance999The paper also
discusses the multi-task case, but we don’t discuss that aspect here..

The inclusion of hysteresis in Dec-HDRQN just combines hysteresis and IDRQN.
That is, since $y-{Q}_{i}^{\theta}({h}_{i},{a}_{i})$ in the IDRQN loss is the
TD error, $\delta$, the network parameters are updated (using gradient
descent) using learning rate $\alpha$ if $\delta>0$, and $\beta$ is used
otherwise.

The concurrent buffer is also relatively straightforward. Concurrent
experience replay trajectories (CERTs), are based on the idea of creating a
joint experience replay buffer and then sampling from that buffer. In
particular, we would like to have a joint replay buffer with joint experience
tuples,
${\mathbf{a}}^{e}_{1},{\mathbf{o}}^{e}_{1},{r}^{e}_{1},\ldots,{\mathbf{a}}^{e}_{t},{\mathbf{o}}^{e}_{t},{r}^{e}_{t}$,
where the superscript here represents the episode number, $e$. Agents could
then sample from this joint buffer to get the local information from the same
episode and time step: ${h}_{i},{a}_{i},{o}_{i},r$ (where ${h}_{i}$ comes from
the internal state of agent $i$’s RNN after passing the local history of
actions and observations until the time step being sampled). Of course, in a
decentralized learning context, agents will not have access to such a joint
buffer, but agents can store their part of the joint buffer by indexing by
episode $e$ and timestep $t$. That is, as seen in Figure 3, agents store their
local trajectories along axes for $e$ and $t$. When an $e$ and $t$ is sampled,
each agent $i$ will sample data from the same episode and timestep, producing
the same data as would be produced with the joint buffer. As long as agents
have the same size buffers and coordinate on the seeds for the random number
generator, this approach can be used for decentralized learning.

Figure 3: Concurrent experience replay trajectories (CERTs) (from (Omidshafiei
et al., 2017))

####  2.3.4 Deep lenient Q-learning

Lenient Q-learning has been extended to the _fully-observable_ deep case in
the form of lenient DQN (Palmer et al., 2018). In this case, the leniency
values are added to the replay buffer of DQN at each step as:
$(s_{t},a_{t},r_{t},s_{t+1},l(s_{t},a_{t}))$ where
$l(s_{t},a_{t})=1-e^{-K*T(\phi(s_{t}),a_{t})}$. To scale to large state
spaces, the approach clusters states using an autoencoder which outputs a hash
$\phi(s)$ for a given state $s$. The method also introduces a temperature
decay schedule after reaching the terminal state and an improved exploration
scheme based on average temperature value.

The approach was shown to perform well in a set of coordinated multi-agent
object transportation problems (CMOTPs). It was not extended to the partially
observable case but it should be possible by using a method that clusters
histories rather than states.

####  2.3.5 Likelihood Q-learning

Distributional Q-learning (Bellemare et al., 2023) has also been used to
improve decentralized MARL. Instead of just learning the expected Q-value as
in traditional Q-learning, distributional RL learns the distribution of
returns that are possible due to stochasticity. Likelihood Q-learning (Lyu and
Amato, 2020) uses the return distribution to determine the likelihood of the
experience (i.e., ${h}_{i},{a}_{i},{o}_{i},r$) given the current estimate,
which they call Time Difference Likelihood (TDL). This information can be used
to help determine if other agents are exploring (i.e., low likelihood and low
value). As a result, the TDL can be used as a multiplier of the learning rate,
causing larger updates for more likely experiences—when other agents are not
exploring.

But some low-likelihood experiences may be good to learn from, such as when
agents have found a high-quality joint action (i.e., low likelihood but high
value). Distributional information can then be used to estimate risk (Morimura
et al., 2010). In the multi-agent context risk-seeking behavior can mean being
optimistic as in hysteretic or lenient learning.

Each of these ideas can be used in isolation or in combination and they can be
used with other decentralized MARL methods to further improve performance. For
instance, the combination of Dec-HDRQN (see 2.3.3) with TDL was shown to
outperform Dec-HDRQN and forms of lenient Q-learning. Incorporating risk can
further improve performance.

##  3 Decentralized policy gradient methods

Single-agent policy gradient and actor-critic methods can similarly be
extended to the decentralized training multi-agent case by allowing each agent
to learn separately. These approaches can scale to larger action spaces and
have stronger (local) convergence guarantees than the value-based counterparts
above.

Policy gradient methods can be used with continuous-action or stochastic
policies. For all approaches, we will assume that we have a stochastic policy
for each agent parameterized by ${\psi}_{i}$, where
${\pi}_{i}^{{\psi}_{i}}({a}_{i}|{h}_{i})$ represents the probability agent $i$
will choose action ${a}_{i}$ given the history ${h}_{i}$ and parameters,
${\psi}_{i}$, $\Pr({a}_{i}|{h}_{i},{\psi}_{i})$. This is in contrast to the
value-based methods in Section 2, where deterministic policies were generated
based on the learned value functions. Like the value-based methods, the
decentralized policy gradient methods also assume agents observe their own
action, ${a}_{i}$, the resulting observation, ${o}_{i}$, and the joint reward,
$r$ at each time step.

###  3.1 Decentralized REINFORCE

REINFORCE (Williams, 1992) is one of the oldest (and simplest) policy gradient
methods. The basic idea is to estimate the value of the policy using Monte
Carlo rollouts and then update the policy using gradient ascent. REINFORCE was
extended to the cooperative multi-agent case by Peshkin et al. (2000).
Importantly, Peshkin et al. (2000) also showed that the joint gradient can be
decomposed into decentralized gradients. That is, decentralized gradient
ascent will be equivalent to joint gradient ascent. Like the value-based
algorithms, ‘independent’ means each agent is learning independently but the
data is generated by all agents from the given policies and all agents make
updates at the same time (i.e., concurrent learning). Convergence to a local
optimum is guaranteed when agents are learning concurrently because they will
apply the same algorithm to the same data at synchronized time steps. This is
in contrast to the value-based methods, which do not have strong convergence
guarantees. These convergence guarantees extend to many other policy gradient
methods (as discussed below).

Pseudocode for a version of decentralized REINFORCE is in Algorithm 3. Here, a
set of stochastic policies, ${\pi}_{i}$, that are parameterized by
${\psi}_{i}$ (e.g., parameters of a neural network), are learned. A learning
rate of $\alpha$ is used (as usual). The method iterates for some number of
episodes, choosing actions from the stochastic policy (which has positive
probability for all actions to ensure proper exploration), observing the joint
reward and local observation at each time step, and storing the episode. Then,
the return is computed for each step of the episode and the parameters of the
policy are updated using the returns and gradient (just like the single-agent
version of REINFORCE). Time steps are explicitly represented in the code to
make return calculation clear. Again, the method can be extended to the
episodic/indefinite-horizon case by replacing the horizon with terminal states
and it isn’t well-defined for the infinite-horizon case (since updating takes
place at the end of episodes).

0: Individual actor models ${\pi}_{i}({a}_{i};{h}_{i})$, parameterized by
${\psi}_{i}$

1: set $\alpha$

2: for all episodes do

3: ${h}_{i,0}\leftarrow\emptyset$ {Empty initial history}

4: $ep\leftarrow\emptyset$ {Empty episode}

5: for $t=0$ to $\mathcal{H}-1$ do

6: Choose ${a}_{i,t}$ at ${h}_{i,t}$ from ${\pi}_{i}({a}_{i};{h}_{i,t})$

7: See joint reward ${r}_{t}$, local observation ${o}_{i,t}${Depends on joint
action $\mathbf{a}$}

8: append ${a}_{i,t},{o}_{i,t},{r}_{t}$ to $ep$

9: ${h}_{i,t+1}\leftarrow{h}_{i,t}{a}_{i,t}{o}_{i,t}${Append new action and
obs to previous history}

10: end for

11: for $t=0$ to $\mathcal{H}-1$ do

12: Compute return at $t$ from $ep$:
$G_{i,t}\leftarrow\sum_{k=t}^{\mathcal{H}-1}\gamma^{k-t}{r}_{k}$

13: Update parameters:
${\psi}_{i}\leftarrow{\psi}_{i}+\alpha\gamma^{t}G_{i,t}\nabla\log{\pi}_{i}({a}_{i}|{h}_{i,t})$

14: end for

15: end for

Algorithm 3 Decentralized REINFORCE for agent $i$ (finite-horizon)

Independent REINFORCE isn’t widely used but serves as a basis for the later
policy gradient approaches as well as theoretical guarantees.

###  3.2 Independent actor critic (IAC)

Since REINFORCE is a Monte Carlo method, it must wait until the end of an
episode to update. Furthermore, it will typically be less sample efficient
than methods that learn a value function. Actor-critic methods have been
developed to combat these issues by learning a policy representation (the
actor) as well as a value function (the critic) (Sutton and Barto, 2018).
Actor-critic methods can use the critic to evaluate the actor without waiting
until the end of the episode and TD-learning to update the critic more
efficiently.

Independent actor-critic (IAC) was first introduced by Foerster et al. (2018)
and it can be thought of as a combination of IQL (or IDRQN) and decentralized
REINFORCE. Each agent learns a policy, ${\pi}_{i}({a}_{i};{h}_{i})$, as well
as a value function such as ${Q}_{i}({h}_{i},{a}_{i})$. In the simplest case
of IAC (where a Q-value is used for the critic), the gradient associated with
the policy parameters ${\psi}_{i}$ can be derived as

$\nabla_{\\!{\psi}_{i}}J=(1-\gamma)E_{\mathbf{h}{},\mathbf{a}\sim\rho(\mathbf{h}{},\mathbf{a})}\left[{Q}_{i}({h}_{i},{a}_{i})\nabla_{\\!{\psi}_{i}}\log{\pi}_{i}^{{\psi}_{i}}({a}_{i}|{h}_{i})\right]\,,$
(8)

assuming a stochastic policy for each agent $i$ that is parameterized by
${\psi}_{i}$, ${\pi}_{i}^{{\psi}_{i}}({a}_{i}|{h}_{i})$. Policies are sampled
according to the on-policy (discounted) visitation probability $\rho$ (which
is a joint visitation probability since concurrent sampling is assumed). This
gradient is very similar to the REINFORCE one but uses a Q-value rather than
the Monte Carlo return (and is shown here with the expectation rather than
just a sample).

In the on-policy, function-approximation (e.g., deep) case, the critic can be
updated as:

$\mathcal{L}({\theta}_{i})=\mathbb{E}_{<{h}_{i},{a}_{i},r,{o}_{i}>\sim\mathcal{D}}\Big{[}\big{(}y-{Q}_{i}^{{\theta}_{i}}({h}_{i},{a}_{i})\big{)}^{2}\Big{]}\text{,
where\,\,
}y=r+\gamma{Q}_{i}^{{\theta}_{i}}({h}_{i}^{\prime},{a}_{i}^{\prime})$ (9)

where ${h}_{i}^{\prime}={h}_{i}{a}_{i}{o}_{i}$ and ${a}_{i}^{\prime}$ is the
action sampled at the next time step using
${\pi}_{i}^{{\psi}_{i}}({a}_{i}^{\prime}|{h}_{i}^{\prime})$ since it is an on-
policy estimate (rather than the max action used in DQN).
${Q}_{i}^{{\theta}_{i}}({h}_{i},{a}_{i})$ represents the Q-function estimate
for agent $i$ using parameters ${\theta}_{i}$ (just like in Section 2).

Pseudocode for IAC is given in Algorithm 4. Because the value function is no
longer being used to select actions but rather just to evaluate the policy, it
is common to instead learn ${V}_{i}({h}_{i})$. And because a model of $V$ is
learned, we denote it $\hat{V}$. Like the REINFORCE case, the algorithm loops
for some number of episodes, choosing actions from the stochastic policy and
seeing the joint reward and local observation at each step. Now, during the
episode, the TD error is calculated and used to update the actor and the
critic using the associated gradients described above. Since V-values are
learned instead of Q-values, the TD error is calculated with
${r}_{t}+\gamma\hat{V}_{i}(h_{i,t+1})-\hat{V}_{i}(h_{i,t})$ rather than
${Q}_{i}$. As a result, a value-based version of Equation 8 is used to update
the actors. Also, a value-based version of Equation 9 is recovered by using
$y=r_{t}+\gamma\hat{V}_{i}(h_{i,t+1})$ and replacing
${Q}_{i}^{{\theta}_{i}}({h}_{i},{a}_{i})$ with $\hat{V}_{i}(h_{i,t})$.

Algorithm 4 Independent Actor-Critic (IAC) (finite-horizon)

0: Individual actor models ${\pi}_{i}({a}_{i}|{h}_{i})$, parameterized by
${\psi}_{i}$

0: Individual critic models $\hat{V}_{i}(h)$, parameterized by ${\theta}_{i}$

1: for all episodes do

2: ${h}_{i,0}\leftarrow\emptyset$ {Empty initial history}

3: for $t=0$ to $\mathcal{H}-1$ do

4: Choose ${a}_{i,t}$ at ${h}_{i,t}$ from ${\pi}_{i}({a}_{i}|{h}_{i,t})$

5: See joint reward ${r}_{t}$, local observation ${o}_{i,t}${Depends on joint
action $\mathbf{a}$}

6: ${h}_{i,t+1}\leftarrow{h}_{i,t}{a}_{i,t}{o}_{i,t}${Append new action and
obs to previous history}

7: Compute value TD error:
$\delta_{i,t}\leftarrow{r}_{t}+\gamma\hat{V}_{i}(h_{i,t+1})-\hat{V}_{i}(h_{i,t})$

8: Compute actor gradient estimate:
$\gamma^{t}\delta_{i,t}\nabla\log{\pi}_{i}(a_{i,t}|h_{i,t})$

9: Update actor parameters ${\psi}_{i}$ using gradient estimate (e.g.,
${\psi}_{i}\leftarrow{\psi}_{i}+\alpha\gamma^{t}\delta_{i,t}\nabla\log{\pi}_{i}(a_{i,t}|h_{i,t})$)

10: Compute critic gradient estimate: $\delta_{i,t}\nabla\hat{V}_{i}(h_{i,t})$

11: Update critic parameters ${\theta}_{i}$ using gradient estimate (e.g.,
${\theta}_{i}\leftarrow{\theta}_{i}+\beta\gamma\delta_{i,t}\nabla\hat{V}_{i}(h_{i,t}))$

12: end for

13: end for

As noted in the value-based (DRQN) case, using an RNN may merge histories of
different lengths into the same representation, resulting in incorrectly timed
value functions in the finite-horizon case. Like the other algorithms, IAC can
be adapted to the episodic or infinite-horizon case by including terminal
states or removing the loop over episodes. IAC is a simple baseline that is
often used and serves as the basis of many other decentralized MARL actor-
critic methods.

###  3.3 Other decentralized policy gradient methods

Any single-agent method can be extended to the decentralized MARL case.
Typically, it just entails including recurrent layers to deal with partial
observability and then training agents concurrently to generate joint data and
synchronize updates. One notable example is IPPO (de Witt et al., 2020; Yu et
al., 2022). IPPO is the extension of single-agent PPO (Schulman et al., 2017)
to the multi-agent case. Forms of IPPO have been shown to outperform many
state-of-the-art MARL methods. It is worth noting that the standard
implementations of IPPO (and the impressive results) use parameter sharing (as
discussed below) so they are not technically decentralized but decentralized
implementations can still perform well (Yu et al., 2022).

##  4 Other topics

##### Concurrent learning

It is very important to note that all of the methods in this section assume
agents are running the same algorithm and perform synchronous updates (i.e.,
at the same time on the same data). Without these assumptions, methods that
have convergence guarantees lose them but may still work well in some domains.
As discussed in relation to DQN (see Section 2.3.2), breaking this
‘concurrent’ learning assumption can cause methods to perform poorly.

##### Parameter sharing

Parameter (or weight) sharing, where agents share the same network for
estimating the value function in value-based methods or policies (and value
functions) in policy gradient methods, is common in cooperative MARL. The data
from each agent can be used to update a single value network for an algorithm
such as DRQN. Agents can still perform differently due to observing different
histories and agent indices can be added to increase specialization (Gupta et
al., 2017). Since parameter sharing requires agents to share networks during
training, it isn’t strictly DTE as it couldn’t be used for online training in
a decentralized fashion. Nevertheless, any of the algorithms in this text can
be extended to use parameter sharing. The resulting algorithms would be a form
of CTDE as the shared network would represent a centralized component.
Nevertheless, these parameter-sharing implementations may be more scalable
than other forms of CTDE, are often simple to implement, and can perform well
(Gupta et al., 2017; Foerster et al., 2018; Yu et al., 2022).

##### Relationship with CTDE

Parameter sharing is one way to exploit a centralized training phase but many
others are possible (e.g., sharing a centralized critic (Lowe et al., 2017;
Foerster et al., 2018) or learning individual value functions from a joint one
(Sunehag et al., 2017; Rashid et al., 2018; Wang et al., 2021)). While CTDE
methods are (by far) the most popular form of MARL, they do not always perform
the best. In fact, since DTE methods typically make the concurrent learning
assumption, they are actually quite close to CTDE methods. This is shown
explicitly in the policy gradient case as the gradient of the joint update is
the same as the decentralized gradient (as described above in Section
3.1)(Peshkin et al., 2000). This phenomenon has been also been studied
theoretically and empirically with modern actor-critic methods (Lyu et al.,
2021, 2023). It turns out that while centralized critic actor-critic methods
are often assumed to be better than DTE actor-critic methods, they are
theoretically the same (with mild assumptions) and often empirically similar
(and sometimes worse). Too much centralized information can sometimes be
overwhelming, harming scalability of centralized-critic methods (Yu et al.,
2022; Lyu et al., 2023). Furthermore, some CTDE methods, such as using a
state-based critic, are fundamentally unsound and can often hurt performance
in partially observable domains (Lyu et al., 2022, 2023). Of course, there are
many different ways of performing centralized training for decentralized
execution, and studying the differences and similarities between DTE and CTDE
variants of algorithms seems like a promising direction for understanding
current methods and developing improved approaches for both cases.

##### Other similar types of learning not considered here

There are a number of papers that focus on ‘fully’ decentralized MARL, such as
Zhang et al. (2018). These methods assume communication between agents during
training and execution. As a result, the assumptions are different than the
ones considered here. I would term these ‘fully’ decentralized as distributed
or networked MARL to make this point more clear. There are also methods that
assume additional coordination. For example, some methods assume agents take
turns learning while the other agents remain fixed (Su et al., 2022; Banerjee
et al., 2012). Such methods require coordinating updates but can converge to
local (i.e., Nash) equilibria.

##  5 Acknowledgements

I thank Roi Yehoshua, Andrea Baisero, and the members of my Lab for Learning
and Planning in Robotics (LLRP) for reading my (very) rough drafts and
providing comments that helped improve the document.

## References

  * Albrecht et al. [2024] S. V. Albrecht, F. Christianos, and L. Schäfer.  _Multi-Agent Reinforcement Learning: Foundations and Modern Approaches_.  MIT Press, 2024.  https://www.marl-book.com.
  * Banerjee et al. [2012] B. Banerjee, J. Lyle, L. Kraemer, and R. Yellamraju.  Sample bounded distributed reinforcement learning for decentralized POMDPs.  In _Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence_ , 2012.
  * Bellemare et al. [2023] M. G. Bellemare, W. Dabney, and M. Rowland.  _Distributional Reinforcement Learning_.  MIT Press, 2023.  http://www.distributional-rl.org.
  * Bernstein et al. [2002] D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein.  The complexity of decentralized control of Markov decision processes.  _Mathematics of Operations Research_ , 27(4):819–840, 2002.
  * Claus and Boutilier [1998] C. Claus and C. Boutilier.  The dynamics of reinforcement learning in cooperative multiagent systems.  In _Proceedings of the National Conference on Artificial Intelligence_ , pages 746–752, 1998.
  * de Witt et al. [2020] C. S. de Witt, T. Gupta, D. Makoviichuk, V. Makoviychuk, P. H. Torr, M. Sun, and S. Whiteson.  Is independent learning all you need in the StarCraft multi-agent challenge?  _arXiv preprint arXiv:2011.09533_ , 2020.
  * Foerster et al. [2016] J. Foerster, I. A. Assael, N. De Freitas, and S. Whiteson.  Learning to communicate with deep multi-agent reinforcement learning.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Foerster et al. [2017] J. Foerster, N. Nardelli, G. Farquhar, T. Afouras, P. H. Torr, P. Kohli, and S. Whiteson.  Stabilising experience replay for deep multi-agent reinforcement learning.  In _Proceedings of the International Conference on Machine Learning_ , pages 1146–1155, 2017.
  * Foerster et al. [2018] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson.  Counterfactual multi-agent policy gradients.  In _Proceedings of the National Conference on Artificial Intelligence_ , 2018.
  * Goldman and Zilberstein [2004] C. V. Goldman and S. Zilberstein.  Decentralized control of cooperative systems: Categorization and complexity analysis.  _Journal of AI Research_ , 22:143–174, 2004.
  * Gupta et al. [2017] J. K. Gupta, M. Egorov, and M. Kochenderfer.  Cooperative multi-agent control using deep reinforcement learning.  In _Adaptive and Learning Agents Workshop at AAMAS_ , 2017.
  * Hausknecht and Stone [2015] M. Hausknecht and P. Stone.  Deep recurrent Q-learning for partially observable MDPs.  _CoRR_ , abs/1507.06527, 2015.
  * Hochreiter and Schmidhuber [1997] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Hussain et al. [2023] A. A. Hussain, F. Belardinelli, and G. Piliouras.  Asymptotic convergence and performance of multi-agent Q-learning dynamics.  In _Proceedings of the International Conference on Autonomous Agents and Multiagent Systems_ , 2023.
  * Jaakkola et al. [1993] T. Jaakkola, M. Jordan, and S. Singh.  Convergence of stochastic iterative dynamic programming algorithms.  In _Advances in Neural Information Processing Systems_ , volume 6, 1993.
  * Kaelbling et al. [1998] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra.  Planning and acting in partially observable stochastic domains.  _Artificial Intelligence_ , 101(1-2):99–134, 1998\.
  * Lauer and Riedmiller [2000] M. Lauer and M. A. Riedmiller.  An algorithm for distributed reinforcement learning in cooperative multi-agent systems.  In _Proceedings of the International Conference on Machine Learning_ , pages 535–542, 2000.
  * Lin [1992] L.-J. Lin.  Self-improving reactive agents based on reinforcement learning, planning and teaching.  _Machine learning_ , 8(3-4):293–321, 1992.
  * Lowe et al. [2017] R. Lowe, Y. I. Wu, A. Tamar, J. Harb, O. Pieter Abbeel, and I. Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Lyu and Amato [2020] X. Lyu and C. Amato.  Likelihood quantile networks for coordinating multi-agent reinforcement learning.  In _Proceedings of the International Conference on Autonomous Agents and Multiagent Systems_ , 2020.
  * Lyu et al. [2021] X. Lyu, Y. Xiao, B. Daley, and C. Amato.  Contrasting centralized and decentralized critics in multi-agent reinforcement learning.  In _Proceedings of the International Conference on Autonomous Agents and Multiagent Systems_ , 2021.
  * Lyu et al. [2022] X. Lyu, Y. Xiao, A. Baisero, and C. Amato.  A deeper understanding of state-based critics in multi-agent reinforcement learning.  In _Proceedings of the National Conference on Artificial Intelligence_ , 2022.
  * Lyu et al. [2023] X. Lyu, A. Baisero, Y. Xiao, B. Daley, and C. Amato.  On centralized critics in multi-agent reinforcement learning.  _Journal of AI Research_ , 77:235–294, 2023.
  * Matignon et al. [2007] L. Matignon, G. J. Laurent, and N. Le Fort-Piat.  Hysteretic Q-learning: An algorithm for decentralized reinforcement learning in cooperative multi-agent teams.  In _Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 64–69, 2007.
  * Mnih et al. [2015] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529, 2015.
  * Morimura et al. [2010] T. Morimura, M. Sugiyama, H. Kashima, H. Hachiya, and T. Tanaka.  Nonparametric return distribution approximation for reinforcement learning.  In _Proceedings of the International Conference on Machine Learning_ , pages 799–806, 2010.
  * Murphy [2000] K. P. Murphy.  A survey of POMDP solution techniques.  Technical report, University of British Columbia, 2000.
  * Nair et al. [2003] R. Nair, M. Tambe, M. Yokoo, D. V. Pynadath, and S. Marsella.  Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings.  In _Proceedings of the International Joint Conference on Artificial Intelligence_ , pages 705–711, 2003.
  * Oliehoek and Amato [2016] F. A. Oliehoek and C. Amato.  _A Concise Introduction to Decentralized POMDPs_.  Springer, 2016.
  * Omidshafiei et al. [2017] S. Omidshafiei, J. Pazis, C. Amato, J. P. How, and J. Vian.  Deep decentralized multi-task multi-agent reinforcement learning under partial observability.  In _Proceedings of the International Conference on Machine Learning_ , pages 2681–2690, 2017.
  * Palmer et al. [2018] G. Palmer, K. Tuyls, D. Bloembergen, and R. Savani.  Lenient multi-agent deep reinforcement learning.  In _Proceedings of the International Conference on Autonomous Agents and Multiagent Systems_ , pages 443–451, 2018.
  * Peshkin et al. [2000] L. Peshkin, K.-E. Kim, N. Meuleau, and L. P. Kaelbling.  Learning to cooperate via policy search.  In _Proceedings of Uncertainty in Artificial Intelligence_ , pages 307–314, 2000.
  * Puterman [1994] M. L. Puterman.  _Markov Decision Processes—Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, Inc., 1994.
  * Rashid et al. [2018] T. Rashid, M. Samvelyan, C. Schroeder, G. Farquhar, J. Foerster, and S. Whiteson.  QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning.  In _Proceedings of the International Conference on Machine Learning_ , pages 4295–4304, 2018.
  * Schulman et al. [2017] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Sen et al. [1994] S. Sen, M. Sekaran, J. Hale, et al.  Learning to coordinate without sharing information.  In _Proceedings of the National Conference on Artificial Intelligence_ , volume 94, pages 426–431, 1994.
  * Su et al. [2022] K. Su, S. Zhou, J. Jiang, C. Gan, X. Wang, and Z. Lu.  MA2QL: A minimalist approach to fully decentralized multi-agent reinforcement learning.  _arXiv preprint arXiv:2209.08244_ , 2022.
  * Sunehag et al. [2017] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, and T. Graepel.  Value-decomposition networks for cooperative multi-agent learning.  arXiv:1706.05296, 2017.
  * Sutton and Barto [2018] R. S. Sutton and A. G. Barto.  _Reinforcement Learning: An Introduction (second edition)_.  The MIT Press, 2018.
  * Tampuu et al. [2017] A. Tampuu, T. Matiisen, D. Kodelja, I. Kuzovkin, K. Korjus, J. Aru, J. Aru, and R. Vicente.  Multiagent cooperation and competition with deep reinforcement learning.  _PloS one_ , 12(4), 2017.
  * Tan [1993] M. Tan.  Multi-agent reinforcement learning: Independent vs. cooperative agents.  In _Proceedings of the International Conference on Machine Learning_ , pages 487–494, 1993.
  * Tuyls et al. [2003] K. Tuyls, K. Verbeeck, and T. Lenaerts.  A selection-mutation model for Q-learning in multi-agent systems.  In _Proceedings of the International Conference on Autonomous Agents and Multiagent Systems_ , pages 693–700, 2003.
  * Wang et al. [2021] J. Wang, Z. Ren, T. Liu, Y. Yu, and C. Zhang.  QPLEX: Duplex dueling multi-agent Q-learning.  In _Proceedings of the International Conference on Learning Representations_ , 2021.
  * Watkins and Dayan [1992] C. J. C. H. Watkins and P. Dayan.  Q-learning.  _Machine Learning_ , 8(3):279–292, May 1992.
  * Wei and Luke [2016] E. Wei and S. Luke.  Lenient learning in independent-learner stochastic cooperative games.  _The Journal of Machine Learning Research_ , 17(1):2914–2955, 2016.
  * Williams [1992] R. J. Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning_ , 8(3-4):229–256, 1992.
  * Wunder et al. [2010] M. Wunder, M. L. Littman, and M. Babes.  Classes of multiagent Q-learning dynamics with $\epsilon$-greedy exploration.  In _Proceedings of the International Conference on Machine Learning_ , pages 1167–1174, 2010.
  * Yu et al. [2022] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu.  The surprising effectiveness of PPO in cooperative multi-agent games.  _Advances in Neural Information Processing Systems_ , 35:24611–24624, 2022.
  * Zhang et al. [2018] K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Basar.  Fully decentralized multi-agent reinforcement learning with networked agents.  In _Proceedings of the International Conference on Machine Learning_ , pages 5872–5881, 10–15 Jul 2018.


# Towards Personalized Bundle Creative Generation with Contrastive Non-
Autoregressive Decoding

Penghui Wei  Alibaba GroupBeijingChina<EMAIL_ADDRESS>,  Shaoguo
Liu  Alibaba GroupBeijingChina<EMAIL_ADDRESS>,  Xuanhua Yang
Alibaba GroupBeijingChina<EMAIL_ADDRESS>,  Liang Wang  Alibaba
GroupBeijingChina<EMAIL_ADDRESS>and  Bo Zheng  Alibaba
GroupBeijingChina<EMAIL_ADDRESS>
(2022)

###### Abstract.

Current bundle generation studies focus on generating a combination of items
to improve user experience. In real-world applications, there is also a great
need to produce bundle creatives that consist of mixture types of objects
(e.g., items, slogans and templates) for achieving better promotion effect. We
study a new problem named bundle creative generation: for given users, the
goal is to generate personalized bundle creatives that the users will be
interested in. To take both quality and efficiency into account, we propose a
contrastive non-autoregressive model that captures user preferences with
ingenious decoding objective. Experiments on large-scale real-world datasets
verify that our proposed model shows significant advantages in terms of
creative quality and generation speed. 00footnotetext: Corresponding author:
S. Liu.

Personalized Bundle Creative Generation

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
45th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 11–15, 2022; Madrid, Spain.††booktitle:
Proceedings of the 45th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’22), July 11–15, 2022, Madrid,
Spain††price: 15.00††isbn: 978-1-4503-8732-3/22/07††doi:
10.1145/3477495.3531909††ccs: Information systems Personalization

##  1\. Introduction

Many online recommendation systems begin to recommend the combination of
multiple items as a bundle to users. E-commerce sites promote personalized
bundled items to enhance user engagement (Zhu et al., 2014; Bai et al., 2019;
Gong et al., 2019). The online gaming platform Steam offers sets of games to
players with a discounted rate (Pathak et al., 2017). Recommending bundles
other than individual items brings benefits: for sellers, the items obtain
more exposure opportunities when they are displayed with other items; for
customers, their interests are broadened and satisfied better. Therefore,
bundle recommendation as well as generation has attracted increasing research
attention in recent years (Vijaikumar et al., 2020; Chang et al., 2021).

Figure 1. An illustration of bundle creative. Unlike ordinary bundles that
contain items, a bundle creative consists of mixture types of objects: items,
slogans and a template.

To achieve better promotion effect, there is also a great need to produce
bundle creatives that consist of mixture types of objects (e.g., for online
advertising and visual recommendation (Deldjoo et al., 2022)). Figure 1 shows
an example that consists of three types of objects: a template (containing
three item slots and two slogan slots), three items and two slogans. For each
bundle, its creative is the content carrier that will be displayed to users.
Appropriate bundle creatives can attract customers and bring improvement on
user experience. Thus sellers will benefit from the service of automatically
generating bundle creatives provided by platforms, especially for small and
medium-sized sellers which may not have much experience.

This paper studies a new problem named personalized bundle creative
generation: for given users as well as their context information (e.g.,
historical interactions), the goal is to generate personalized bundle
creatives that the users will be interested in. This problem is faced with the
following challenges: (i) Creative-level quality: We not only need to mine the
combination of items from users’ historical interactions, but also consider
the creative as a whole to meet user preference and ensure creative quality.
(ii) Generation efficiency: The generation speed of bundle creatives is also a
key factor of models, especially in real-time service. Current bundle
generation models usually employ sequential mechanism to produce each item
step-by-step (Bai et al., 2019; Gong et al., 2019; Chang et al., 2021), which
is inefficient to real-time applications and the quality is affected by item
order. Such challenges make it difficult for existing bundle generation models
(i.e., taking item as the only type of object) to tackle the bundle creative
generation problem. Although there are a few approaches for ad creative
optimization (Chen et al., 2021), they aim to composite multiple elements of a
creative for a given item (that is, this task does not need to mine item or
item combination from user context).

With the aim of taking both creative-level quality and generation efficiency
into account, in this paper we propose a contrastive non-autoregressive
decoding model (Conna) for bundle creative generation, which captures user
preferences with ingenious decoding objective. Our Conna model is an encoder-
decoder architecture. A type-aware encoder adopts self-attention to learn the
representations for mixture types of candidate objects. A non-autoregressive
decoder generates all objects of a creative in parallel, which is unaware of
object ordering and furthest improves decoding efficiency. To ensure creative-
level quality that meets user preferences, the Conna model is optimized via a
contrastive learning objective, which measures the quality of generated
creatives by considering user positive/negative feedbacks. The main
contributions are:

  * •

To our knowledge, this work is the first attempt that studies the problem of
bundle creative generation, which makes effort to improve promotion effect in
real world applications. We will release our datasets to facilitate further
research.

  * •

We propose a contrastive non-autoregressive decoding model (Conna), which
takes both creative-level quality and generation efficiency into account for
bundle creative generation.

  * •

Experiments verify that our Conna model shows significant advantages in terms
of creative quality and generation speed.

Figure 2. Overview of our contrastive non-autoregressive model Conna for
personalized bundle creative generation.

##  2\. Problem Definition

Let
$\mathcal{O}=\mathcal{O}_{\mathrm{i}}\cup\mathcal{O}_{\mathrm{s}}\cup\mathcal{O}_{\mathrm{t}}$
denote the candidate object set, where $\mathcal{O}_{\mathrm{i}}$ /
$\mathcal{O}_{\mathrm{s}}$ / $\mathcal{O}_{\mathrm{t}}$ denotes candidate
items / slogans / templates.111The problem can be generalized to any mixture
types of objects. For each bundle creative, we assume that the number of items
/ slogans / templates is $I$ / $S$ / $T$ (for the one in Figure 1, $I=3,S=2$
and $T=1$).

We have an interaction matrix between users and bundle creatives, where each
element denotes whether the user has positive feedback (i.e., click) to the
bundle creative. The goal of personalized bundle creative generation is to
learn a model $p(b\mid u,\mathcal{O})$: given user $u$’s context information
and candidate objects $\mathcal{O}$, the model produces a bundle creative $b$
that the user is most satisfied with it. Consider that the size of candidate
item set $\mathcal{O}_{\mathrm{i}}$ is usually large, following (Bai et al.,
2019) we resort to the user’s historical clicked items
$\mathcal{O}_{{\mathrm{i}}}^{u}$, other than the whole set
$\mathcal{O}_{\mathrm{i}}$. Thus it is possible that a few items in $b$ are
not contained in $\mathcal{O}^{u}_{\mathrm{i}}$.

##  3\. Proposed Model

We propose a contrastive non-autoregressive model Conna for bundle creative
generation. Figure 2 gives an overview of Conna, which contains a type-aware
encoder and a non-autoregressive decoder to improve generation efficiency. It
is optimized via a contrastive learning objective to ensure creative-level
quality.

###  3.1. Encoding Mixture Types of Candidates

The input of Conna model contains four parts: the user $u$, the historical
clicked item set
$\mathcal{O}_{{\mathrm{i}}}^{u}=\left\\{i^{u}_{1},i^{u}_{2},\ldots,i^{u}_{K}\right\\}$
of this user, candidate slogan set
$\mathcal{O}_{\mathrm{s}}=\left\\{s_{1},s_{2},\ldots,s_{|\mathcal{O}_{\mathrm{s}}|}\right\\}$
and candidate template set
$\mathcal{O}_{\mathrm{t}}=\left\\{t_{1},t_{2},\ldots,t_{|\mathcal{O}_{\mathrm{t}}|}\right\\}$.
For convenience, we denote the input as a unified sequence
$\left(u;i^{u}_{1},\ldots,i^{u}_{K};s_{1},\ldots,s_{|\mathcal{O}_{\mathrm{s}}|};t_{1},\ldots,t_{|\mathcal{O}_{\mathrm{t}}|}\right)$,
next we will show that the encoder of Conna is unaware of such ordering of
objects in a bundle creative.

Conna employs a type-aware encoder to learn representations for mixture types
of candidates, which consists of an embedding layer and several self-attention
layers (Vaswani et al., 2017). Specifically, for each object of the input
sequence, the embedding layer computes two embeddings to represent the object.
The first is content embedding: for user, item, slogan and template IDs, we
have four content embedding matrices $\bm{U},\bm{I},\bm{S}$ and $\bm{T}$ that
transform each object ID to its embedding. The second is type embedding: we
maintain a type embedding matrix
$\bm{E}=\left[\bm{e}^{(\mathrm{u})};\bm{e}^{(\mathrm{i})};\bm{e}^{(\mathrm{s})};\bm{e}^{(\mathrm{t})}\right]\in\mathbb{R}^{d\times
4}$, where each embedding is for one type (i.e., user, item, slogan and
template). For each object in the input sequence, the embedding layer adds its
content embedding and type embedding:

(1) $\displaystyle\bm{\hat{u}}$
$\displaystyle=\bm{u}+\bm{e}^{(\mathrm{u})}\,,\qquad\qquad\qquad\quad\bm{\hat{i}}_{k}^{u}=\bm{i}^{u}_{k}+\bm{e}^{(\mathrm{i})}\
\ (k\in[1,K])\,,$ $\displaystyle\bm{\hat{s}}_{i}$
$\displaystyle=\bm{s}_{i}+\bm{e}^{(\mathrm{s})}\ \
(i\in[1,|\mathcal{O}_{\mathrm{s}}|])\,,\quad\bm{\hat{t}}_{j}=\bm{t}_{j}+\bm{e}^{(\mathrm{t})}\
\ (j\in[1,|\mathcal{O}_{\mathrm{t}}|])\,,$

where $\bm{u},\bm{i}_{k}^{u},\bm{s}_{i}$ and $\bm{t}_{j}$ denote content
embeddings for $u,i_{k}^{u},s_{i}$ and $t_{j}$.

The encoder then adopts $L$ self-attention layers to learn representations for
each candidate object. Let
$\bm{H}^{l}\in\mathbb{R}^{d\times(1+K+|\mathcal{O}_{\mathrm{s}}|+|\mathcal{O}_{\mathrm{t}}|)}$
denote the $l$-th layer’s input, where the input of the first layer is
$\bm{H}^{1}=\left(\bm{\hat{u}},\bm{\hat{i}}_{1}^{u},\ldots,\bm{\hat{i}}_{K}^{u},\bm{\hat{s}}_{1},\ldots,\bm{\hat{s}}_{|\mathcal{O}_{\mathrm{s}}|},\bm{\hat{t}}_{1},\ldots,\bm{\hat{t}}_{|\mathcal{O}_{\mathrm{t}}|}\right)$.
We use Pre-LN self-attention operation (Klein et al., 2017) to produce output
$\bm{H}^{l+1}$, which applies layer normalization before multi-head attention
and position-wise feed-forward network to achieve faster convergence. The
encoder of Conna produces representations $\bm{H}^{L+1}$ for each input
object,222Although we may design a sophisticated encoder (e.g., based on graph
neural networks (Chang et al., 2021; Wei et al., 2021)), the main focus of
this work is the generation process, thus we employ a simple-yet-effective
design of encoder. which is unaware of each object’s position in the input
sequence.

###  3.2. Non-Autoregressive Creative Generation

After encoding candidate objects, the decoder generates mixture types of
objects forming a bundle creative to meet user preferences. Let
$b=\left\\{b^{(\mathrm{i})}_{1},b^{(\mathrm{i})}_{2},\ldots,b^{(\mathrm{i})}_{I};b^{(\mathrm{s})}_{1},b^{(\mathrm{s})}_{2},\ldots,b^{(\mathrm{s})}_{S};b^{(\mathrm{t})}\right\\}$
denote a bundle creative that the user $u$ has positive feedback, where
$b^{(\mathrm{i})}_{*}$, $b^{(\mathrm{s})}_{*}$ and $b^{(\mathrm{t})}$ denote
item, slogan and template, respectively. A few items may not be contained in
user historical clicked item set $\mathcal{O}^{u}_{\mathrm{i}}$.

Traditional autoregressive decoder generates each object one-by-one, which
factorizes the generation probability of $b$ to the multiplying of conditional
probabilities. However, the factorization is affected by both the order of
{items, slogans, template} and the order within items / slogans, yet we do not
have a ”ground-truth” ordering in fact. Besides, the efficiency is limited,
because it generates each object conditioned on previously generated ones.

####  3.2.1. Non-Autoregressive Decoder Architecture

We furthest improve efficiency via modeling the bundle creative probability
as:

(2) $\small p(b\mid u,\mathcal{O})=\prod_{j=1}^{I}p(b^{(\mathrm{i})}_{j}\mid
u,\mathcal{O})\cdot\prod_{j=1}^{S}p(b^{(\mathrm{s})}_{j}\mid
u,\mathcal{O})\cdot p(b^{(\mathrm{t})}\mid u,\mathcal{O})$

Based on this factorization, the generation is unaware of the ordering, and at
inference time it computes all distributions in parallel.

Let $B=I+S+1$ denote object number. For convenience, we define that $I$ items
are generated from the 1st to $I$-th positions, $S$ slogans are generated from
the $(I+1)$-th to $(I+S)$-th positions, and the template is generated by the
$B$-th position. In fact our decoder is not affected by this order due to non-
autoregressive nature.

Specifically, the decoder architecture of our Conna model consists of an
embedding layer, several attention layers and an output layer. The embedding
layer aims to produce $B$ “trigger embeddings” that guide the generation
process. The trigger embedding of the $j$-th position ($j\in[1,B]$) is the sum
of two parts:

  * •

type embedding, which represents the object type of this position (e.g., for
$1\leq j\leq I$ we take $\bm{e}^{(\mathrm{i})}$ from $\bm{E}$ because the
object type is item; for $I+1\leq j\leq I+S$ we take $\bm{e}^{(\mathrm{s})}$).

  * •

type-specific positional embedding, where we maintain three positional
embedding matrices $\bm{P}^{(\mathrm{i})}\in\mathbb{R}^{d\times
I},\bm{P}^{(\mathrm{s})}\in\mathbb{R}^{d\times S}$ and
$\bm{P}^{(\mathrm{t})}\in\mathbb{R}^{d\times 1}$ for all types. For $1\leq
j\leq I$, we take the $j$-th column from $\bm{P}^{(\mathrm{i})}$ to represent
that this position need to generate the $j$-th item. Similarly, for $I+1\leq
j\leq I+S$, we take the $(j-I)$-th column from $\bm{P}^{(\mathrm{s})}$ to
represent that this position need to generate the $(j-I)$-th slogan.

The use of type-specific positional embedding ensures that the decoder can
distinguish different objects from the same type during generation, avoiding
the situation of generating repeat objects.

Then attention layers employ self-attention and encoder-decoder cross
attention to learn each position’s representation (Vaswani et al., 2017). We
remove causal mask in standard Transformer decoder, because we no longer need
prevent to attend previously positions. In contrast, the decoder considers
pair-wise relationships to globally modeling.

Finally, the output layer employs position-wise feed-forward operation with
softmax to compute each position’s probability distribution over the candidate
set of this position’s object type. Let
$\left\\{\bm{\hat{b}}^{(\mathrm{i})}_{1},\ldots,\bm{\hat{b}}^{(\mathrm{i})}_{I};\bm{\hat{b}}^{(\mathrm{s})}_{1},\ldots,\bm{\hat{b}}^{(\mathrm{s})}_{S};\bm{\hat{b}}^{(\mathrm{t})}\right\\}$
be each position’s predicted distribution, where
$\bm{\hat{b}}^{(\mathrm{i})}_{*}\in\mathbb{R}^{|\mathcal{O}_{\mathrm{i}}|}$,
$\bm{\hat{b}}^{(\mathrm{s})}_{*}\in\mathbb{R}^{|\mathcal{O}_{\mathrm{s}}|}$
and $\bm{\hat{b}}^{(\mathrm{t})}\in\mathbb{R}^{|\mathcal{O}_{\mathrm{t}}|}$.

###  3.3. Optimization

A straightforward objective is the independent cross-entropy (XEnt) losses of
all positions by comparing predicted distributions and $b$:

(3)
$\small\mathcal{L}^{(\mathrm{i})}+\mathcal{L}^{(\mathrm{s})}+\mathcal{L}^{(\mathrm{t})}=\sum_{j=1}^{I}\mathsf{XEnt}\left(\bm{\hat{b}}^{(\mathrm{i})}_{j},b^{(\mathrm{i})}_{j}\right)+\sum_{j=1}^{S}\mathsf{XEnt}\left(\bm{\hat{b}}^{(\mathrm{s})}_{j},b^{(\mathrm{s})}_{j}\right)+\mathsf{XEnt}\left(\bm{\hat{b}}^{(\mathrm{t})},b^{(\mathrm{t})}\right)$

However, in a bundle creative, because objects from same type are unordered,
such optimization will penalize the true predictions that reorder
items/slogans: for instance, if we have:

$\small{b^{(\mathrm{i})}_{1}=\mathrm{item}_{X},\ \
b^{(\mathrm{i})}_{2}=\mathrm{item}_{Y},\ \
b^{(\mathrm{i})}_{3}=\mathrm{item}_{Z}}\vspace{-1em}$
$\small{\arg\max\bm{\hat{b}}^{(\mathrm{i})}_{1}=\mathrm{item}_{Z},\
\arg\max\bm{\hat{b}}^{(\mathrm{i})}_{2}=\mathrm{item}_{X},\
\arg\max\bm{\hat{b}}^{(\mathrm{i})}_{3}=\mathrm{item}_{Y}}$

the model produces true prediction, but the above learning objective will
suggest that all positions are wrongly predicted.

####  3.3.1. Set-based Learning Objective

To avoid above inaccurate penalty, inspired by (Carion et al., 2020; Du et
al., 2021) we propose a set-based learning objective for training the Conna
model. Formally, consider the item type, we construct all possible
permutations of $I$ items in $b$ as a permutation space
$\mathbf{B}^{(\mathrm{i})}=\left\\{\mathcal{B}^{(\mathrm{i})}_{1},\ldots,\mathcal{B}^{(\mathrm{i})}_{I!}\right\\}$,
where the item set of each permutation $\mathcal{B}^{(\mathrm{i})}_{*}$ is
same (i.e.,
$\left\\{b^{(\mathrm{i})}_{1},\ldots,b^{(\mathrm{i})}_{I}\right\\}$). We
employ Hungarian algorithm (Kuhn, 1955) to efficiently search a permutation
from $\mathbf{B}^{(\mathrm{i})}$ that has minimal XEnt value:

(4)
$\mathcal{L}^{(\mathrm{i})}_{\mathrm{set}}(b)=\min\left\\{\mathcal{L}^{(\mathrm{i})}\left(\mathcal{B}^{(\mathrm{i})}_{*}\right)\right\\}_{\mathcal{B}^{(\mathrm{i})}_{*}\in{\mathbf{B}}^{(\mathrm{i})}}$

where $\mathcal{L}^{(\mathrm{i})}\left(\mathcal{B}^{(\mathrm{i})}_{*}\right)$
means that we use the permutation $\mathcal{B}^{(\mathrm{i})}_{*}$ instead of
original
$\left(b^{(\mathrm{i})}_{1},b^{(\mathrm{i})}_{2},\ldots,b^{(\mathrm{i})}_{I}\right)$
as ground-truth to compute the $\mathcal{L}^{(\mathrm{i})}$ in Equation 3. For
slogan type, $\mathcal{L}^{(\mathrm{s})}_{\mathrm{set}}$ can be similarly
defined.

Through the set-based objective for all types of objects:

(5)
$\mathcal{L}_{\mathrm{set}}(b)=\mathcal{L}^{(\mathrm{i})}_{\mathrm{set}}(b)+\mathcal{L}^{(\mathrm{s})}_{\mathrm{set}}(b)+\mathcal{L}^{(\mathrm{t})}(b)$

the optimization procedure does not penalize any true predictions.

####  3.3.2. Contrastive Learning Objective

With the aim of considering the generated creative as a whole to ensure
creative-level quality, we incorporate the bundle creatives that are exposed
to the user $u$ but are not clicked as negative instances $\\{b_{-}\\}$.
Specifically, we propose to explicitly model the generation probabilities of
both positive and negative bundle creatives during optimization. A margin-
based loss is used to maximize the probability gap of generating positive
bundle creative $b$ and negative ones $\\{b_{-}\\}$:

(6)
$\mathcal{L}_{\mathrm{cl}}(b,b_{-})=\sum_{b_{-}}\max\biggl{\\{}0,-\biggl{(}\mathcal{L}_{\mathrm{set}}(b_{-})-\mathcal{L}_{\mathrm{set}}(b)\biggr{)}+\gamma\biggr{\\}}$

where $\gamma$ denotes the margin hyperparameter.

Overall, the Conna model is optimized via the following objective, where
$\lambda$ balances two terms:

(7)
$\mathcal{L}_{\mathrm{set}}(b)+\lambda\mathcal{L}_{\mathrm{cl}}(b,b_{-})\,.$

####  3.3.3. Inference

At inference time, the Conna model produces bundle creative via generating all
objects in parallel, where $\mathrm{argmax}$ operation is applied to each
position’s predicted distribution ($\bm{\hat{b}}^{(\mathrm{i})}_{*}$,
$\bm{\hat{b}}^{(\mathrm{s})}_{*}$ and $\bm{\hat{b}}^{(\mathrm{t})}$).

##  4\. Experiments

###  4.1. Experimental Setup

Datasets We collected real world user feedbacks from a large e-commerce
advertising platform to construct large-scale bundle creative (BC) datasets
(Figure 1 shows the style of BCs). The overall feedback log contains 7 million
instances, where 100k of them are positive instances (i.e., clicked by users,
in which each user has clicked on 1.03 BC on average). We split it to
training/development/test sets via timestamp with the proportion of 7:1:2. To
investigate the dataset size’s impact, we perform sampling to training set
with a ratio of 30% to obtain a small version, named BC-S dataset, and the
full dataset is named BC-L.

Competitors We compare the following models designed for bundle creative
generation. They use same encoder architecture, and the differences are
decoder and learning objective.

(i) MultiDec: It employs three independent autoregressive decoders (RNNs) to
produce items, slogans and template respectively.

(ii) UnifiedDec: It employs a unified decoder to autoregressively generate
items, then slogans, and finally template.333We empirically find that this
ordering performs best. See section 4.3.2. At each time step we need to
generate a specific type of object, thus we only generate from this type’s
vocabulary and mask other types’ vocabularies to avoid generating wrong type.

(iii) PointerNet: Similar to the approach in (Gong et al., 2019), a pointer
mechanism (Vinyals et al., 2015) is equipped to the decoder in UnifiedDec,
which can copy element from input side by a gating mechanism.

(iv) RL-PointerNet: It follows (Gong et al., 2019) that trains a reward
estimator to represent creative-level quality, and fine-tunes the PointerNet
via REINFORCE (Williams, 1992).

(v) RL-Transformer: It replaces the decoder of RL-PointerNet from RNN to
standard Transformer decoder.

(vi) Conna is our proposed non-autoregressive model.

For fair comparison, all models have same configuration (layer number $L=3$,
dimension $d=256$, the size of user historical clicked items is 50). For each
positive instance we sample up to three negative ones for
$\mathcal{L}_{\mathrm{cl}}$, and we set $\gamma=1$ and $\lambda=0.5$.

Evaluation Metrics Let $b$ ($\hat{b}$) denote gold (generated) bundle
creative, where $b^{(\mathrm{i})}$/$b^{(\mathrm{s})}$/$b^{(\mathrm{t})}$
denotes the item set / slogan set / template of $b$, and
$\hat{b}^{(\mathrm{i})}$/$\hat{b}^{(\mathrm{s})}$/$\hat{b}^{(\mathrm{t})}$
denotes that of $\hat{b}$. We evaluate each model from three aspects: quality,
diversity and efficiency.

(1) For evaluating the creative quality, we design HitRatio-based metric.
Specifically, a weighted sum formulation is defined as:

$\mathrm{HitRatio}=\frac{I}{I+S+1}\cdot\frac{|b^{(\mathrm{i})}\cap\hat{b}^{(\mathrm{i})}|}{I}+\frac{S}{I+S+1}\cdot\frac{|b^{(\mathrm{s})}\cap\hat{b}^{(\mathrm{s})}|}{S}+\frac{|b^{(\mathrm{t})}\cap\hat{b}^{(\mathrm{t})}|}{I+S+1}$

(2) To evaluate item diversity in a generated creative, we design the metric
$\mathrm{Diversity}$:

$\mathrm{Diversity}=\frac{1}{|I|(|I|-1)}\sum_{\hat{b}^{(\mathrm{i})}_{j},\hat{b}^{(\mathrm{i})}_{j^{\prime}}\in\hat{b}^{(\mathrm{i})}}\left(1-\mathbb{I}\left(\hat{b}^{(\mathrm{i})}_{j}=\hat{b}^{(\mathrm{i})}_{j^{\prime}}\right)\right)$

This metric shows the basic utility the generative bundle creative, because
repeated object is unsatisfactory.

(3) To evaluate efficiency of a model, we compare the speedup over the
autoregressive model RL-Transformer when decoding a single bundle creative.

Table 1. Results on personalized bundle creative generation (HR. and Div. denote HitRatio and Diversity, respectively). The improvement of Conna on HR. is statistically significant to the second-best model. Model | BC-S Dataset | BC-L Dataset |
---|---|---|---
(Same Encoder) | HR. | Div. | HR. | Div. | Speedup
MultiDec | 0.3806 | 0.9147 | 0.4576 | 0.9349 |  1.6$\times$
UnifiedDec | 0.4622 | 0.9483 | 0.5721 | 0.9596 |  1.3$\times$
PointerNet | 0.4776 | 0.9335 | 0.6079 | 0.9709 |  1.2$\times$
RL-PointerNet | 0.5107 | 0.9474 | 0.6209 | 0.9726 |  1.2$\times$
RL-Transformer | 0.5317 | 0.9542 | 0.6411 | 0.9825 |  1$\times$
Conna (Ours) | 0.5431 | 0.9642 | 0.6564 | 0.9802 | 2.8$\times$

###  4.2. Main Results

Table 1 shows the comparison results of all comparative models for
personalized bundle creative generation. By comparing MultiDec and UnifiedDec,
the results show that independent decoders cannot capture the relationship
among object types during generation, and MultiDec performs poorly on creative
quality. Thus generating mixture types of objects is a challenging problem.
PointerNet employs pointer to select elements from encoder side during
decoding, and outperforms UnifiedDec. This verifies that the generation
performance benefits from the improvement of decoding mechanism, as shown in
previous work (Gong et al., 2019).

By training an extra reward estimator that provides creative-level quality,
RL-PointerNet further outperforms PointerNet by a large margin through a fine-
tuning process with the objective of maximizing expected reward of the
generated bundle creatives. This shows that taking creative-level quality into
account for creative generation is effective to improve the overall
performance of bundle creative generation. RL-Transformer employs a self-
attention based decoder to model the dependency among generated objects, and
performs much better than traditional RNN-based RL-PointerNet. This
demonstrates that the Transformer architecture is suitable to bundle creative
generation task which needs to decode mixture of types of objects.

Our proposed Conna model employs a non-autoregressive decoder that furthest
improves decoding efficiency for bundle creatives, and considers creative-
level quality during training with a contrastive learning objective. It
achieves the best performance among all competitors in terms of both
generation quality (HitRatio) and effiency (Speedup). This indicates that the
Conna model possesses the ability of balancing effectiveness and efficiency
for bundle creative generation task.

Besides, note that our Conna model also has advantage in terms of training
efficiency compared to RL-based models. The contrastive learning objective is
coupled with the set-based generation objective in an end-to-end manner, which
is unlike other RL-based comparative models that need three steps to produce
the final model: 1) train a reward estimator, 2) train a generation model, 3)
finally fine-tune the trained model guided by reward estimator. Therefore, the
proposed Conna model shows advantages on multiple aspects compared to other
models.

###  4.3. Discussion

####  4.3.1. Ablation Study

The key of Conna is two-fold: the first is the contrastive objective that
utilizes negative bundle creatives during optimization, and the second is the
set-based objective that does not penalize any true predictions during
optimization. To verify the effectiveness of them in our Conna, we conduct
ablation experiments, in which the first variant removes the constrastive
objective during training, and the second variant further replaces the set-
based objective to the independent XEnt objective of Equation 3.

Table 2 shows the results. We observe that the contrastive objective
contributes to the overall quality of Conna. Moreover, by using the set-based
objective, the generation performance achieves further improvement. In terms
of the input design of our decoder, type-specific positional embedding also
brings uplift to the HitRatio, demonstrating its effect to decoder input.

Table 2. Ablation experiments of the Conna model. Model | HR. | Div.
---|---|---
Conna (full model) | 0.6564 | 0.9802
[2pt/1.2pt] w/o contrastive objective | 0.6194 | 0.9822
w/o set-based objective, w/ independent XEnt | 0.5893 | 0.9822

Figure 3. Results with different ordering of object types.

####  4.3.2. Analysis on Ordering of Object Types

Autoregressive-based models need a pre-defined ordering of object types to
produce each object in a bundle creative one-by-one. In contrast, our Conna is
unaware of that due to the non-autoregressive nature.

We compare the performance of two competitors w.r.t. different ordering of
object types. As the results in Figure 3, we observe that Conna is indeed not
affected by the ordering, verifying the advantage of non-autoregressive
decoding for bundle creative generation.

##  5\. Conclusion

This work studies a new problem of personalized bundle creative generation. To
take both quality and efficiency into account, we propose a contrastive non-
autoregressive model that captures user preferences with ingenious decoding
objective. Results verify that it shows significant advantages in terms of
creative quality and generation speed.

In future work, we shall explore how to avoid conflicting and unfavorable
items to be grouped together during generation.

## Acknowledgments

We thank all the anonymous reviewers to their insightful comments.

## References

  * (1)
  * Bai et al. (2019) Jinze Bai, Chang Zhou, Junshuai Song, Xiaoru Qu, Weiting An, Zhao Li, and Jun Gao. 2019.  Personalized bundle list recommendation. In _The World Wide Web Conference_. 60–71.
  * Carion et al. (2020) Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. 2020.  End-to-end object detection with Transformers. In _European Conference on Computer Vision_. 213–229.
  * Chang et al. (2021) Jianxin Chang, Chen Gao, Xiangnan He, Depeng Jin, and Yong Li. 2021.  Bundle Recommendation and Generation with Graph Neural Networks.  _IEEE Transactions on Knowledge and Data Engineering_ (2021).
  * Chen et al. (2021) Jin Chen, Ju Xu, Gangwei Jiang, Tiezheng Ge, Zhiqiang Zhang, Defu Lian, and Kai Zheng. 2021.  Automated Creative Optimization for E-Commerce Advertising. In _Proceedings of the Web Conference 2021_. 2304–2313.
  * Deldjoo et al. (2022) Yashar Deldjoo, Tommaso Di Noia, Daniele Malitesta, and Felice Antonio. 2022.  Leveraging Content-Style Item Representation for Visual Recommendation. In _The 44th European Conference on Information Retrieval_.
  * Du et al. (2021) Cunxiao Du, Zhaopeng Tu, and Jing Jiang. 2021.  Order-agnostic cross entropy for non-autoregressive machine translation. In _International Conference on Machine Learning_. 2849–2859.
  * Gong et al. (2019) Yu Gong, Yu Zhu, Lu Duan, Qingwen Liu, Ziyu Guan, Fei Sun, Wenwu Ou, and Kenny Q Zhu. 2019\.  Exact-k recommendation via maximal clique optimization. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 617–626.
  * Klein et al. (2017) Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander M Rush. 2017.  OpenNMT: Open-Source Toolkit for Neural Machine Translation. In _Proceedings of ACL 2017, System Demonstrations_. 67–72.
  * Kuhn (1955) Harold W Kuhn. 1955\.  The Hungarian method for the assignment problem.  _Naval research logistics quarterly_ 2, 1-2 (1955), 83–97.
  * Pathak et al. (2017) Apurva Pathak, Kshitiz Gupta, and Julian McAuley. 2017\.  Generating and personalizing bundle recommendations on Steam. In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 1073–1076.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need. In _Advances in neural information processing systems_. 5998–6008.
  * Vijaikumar et al. (2020) M Vijaikumar, Shirish Shevade, and M Narasimha Murty. 2020\.  GRAM-SMOT: Top-n personalized bundle recommendation via graph attention mechanism and submodular optimization. In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. 297–313.
  * Vinyals et al. (2015) Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015\.  Pointer Networks.  _Advances in Neural Information Processing Systems_ 28 (2015), 2692–2700.
  * Wei et al. (2021) Penghui Wei, Jiahao Zhao, and Wenji Mao. 2021.  A Graph-to-Sequence Learning Framework for Summarizing Opinionated Texts.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ 29 (2021), 1650–1660.
  * Williams (1992) Ronald J Williams. 1992\.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ 8, 3 (1992), 229–256.
  * Zhu et al. (2014) Tao Zhu, Patrick Harrington, Junjun Li, and Lei Tang. 2014\.  Bundle recommendation in ecommerce. In _Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval_. 657–666.