# Cluster-Based Control of Transition-Independent MDPs

Carmel Fiscko1, Soummya Kar1, and Bruno Sinopoli2 1Carmel Fiscko and Soummya
Kar are with the Dept. of Electrical and Computer Engineering at Carnegie
Mellon University in Pittsburgh, PA<EMAIL_ADDRESS><EMAIL_ADDRESS>Sinopoli is with the Dept. of Electrical and
Systems Engineering at Washington University in St. Louis, MO.
<EMAIL_ADDRESS>
###### Abstract

This work studies the ability of a third-party influencer to control the
behavior of a multi-agent system. The controller exerts actions with the goal
of guiding agents to attain target joint strategies. Under mild assumptions,
this can be modeled as a Markov decision problem and solved to find a control
policy. This setup is refined by introducing more degrees of freedom to the
control; the agents are partitioned into disjoint clusters such that each
cluster can receive a unique control. Solving for a cluster-based policy
through standard techniques like value iteration or policy iteration, however,
takes exponentially more computation time due to the expanded action space. A
solution is presented in the Clustered Value Iteration (CVI) algorithm, which
iteratively solves for an optimal control via a “round robin” approach across
the clusters. CVI converges exponentially faster than standard value
iteration, and can find policies that closely approximate the MDP’s true
optimal value. For MDPs with separable reward functions, CVI will converge to
the true optimum. While an optimal clustering assignment is difficult to
compute, a “good” clustering assignment for the agents may be found with a
greedy splitting algorithm, whose associated values form a monotonic,
submodular lower bound to the values of optimal clusters. Finally, these
control ideas are demonstrated on simulated examples.

##  1 Introduction

Social media users, robot swarms, and financial transactions are examples of
system behavior driven by the decisions of individuals. A person’s posts
online reflect their own opinions, yet they are influenced by their friends,
trends, and current events. These decisions, in turn, affect the path of
future posts and trends. Within cooperative robotics, a central objective must
be completed, yet each robot’s path must consider those of its peers. On the
competitive side, businesses weigh their rivals’ actions to likewise position
themselves to an advantage. Each of these examples show the importance of each
agent’s goals, peers, and reactions to each other. Understanding the decision-
making processes of the individual agents can reveal mechanisms by which the
system evolves. To control system-wide behavior, therefore, one must therefore
understand how to influence the agents’ decision-making processes.

###  1.1 Multi-Agent Systems

Such groups of agents are often modeled as multi-agent systems (MAS), which
widely appear in distributed learning applications. In this paper, we adopt
the definition of agent from [1]: “we consider an agent to be an entity with
goals, actions, and domain knowledge, situated in an environment. The way it
acts is called its ‘behavior.’” These agents can model applications such as
computer networks, smart grids, and cyberphysical systems, in addition to the
aforementioned models of social media, robots, and finance [2]. Natural
questions of these topics include control, security, coordination, and
scalability.

One approach to studying MAS uses tools developed in game theory to understand
each agents’ decision-making process [3]. In a game model, an individual is
endowed with a utility function that rates the goodness of a potential action
in the current world. Armed with these utilities, the agent chooses their next
action, possibly sampled according to a personal rule. The collectively played
action across the system, known as the joint action or joint strategy, thus
evolves stochastically as agents consider their goals and their peers. A
competitive game has these agents pitted against each other, selfishly trying
to maximize their own utilities. The outcome of this game may be described
with optimal actions and Nash equilibria, in which agents self-reinforce game-
play at the same action. Subfields of these games include auctions, regret
minimization, and network games. In contrast, cooperative games consider
coalitions of agents who collaborate to maximize a group payoff, and outcomes
are described as coalition structures. Another related topic is mechanism
design, where a designer chooses economic or social to induce a game outcome
[4].

This last idea of control of MAS ties into reinforcement learning (RL). Under
assumptions or a construction of Markovian dynamics, a MAS may be considered
as a Markov decision process (MDP) [5]. This formulation allows a central
controller to influence the agents’ decision-making processes by changing
their state to state transition kernels. From the game theory perspective,
this influence may be viewed as the controller changing the players’ utility
functions, and thus making future actions look better or worse. The controller
acts to achieve some personal goal, most often stated as maximizing the
expected sum of rewards received from visiting states.

This work is closely related to, but distinct from, multi-agent reinforcement
learning (MARL). In MARL problems, agents attempt to maximize a long-term
reward by optimizing their own decision-making process via exploring an
environment or talking to other agents[6]. These agents may be cooperative,
competitive, or agnostic to their peers [7]. Again, the understanding of the
agents may come from game theory [8]. Many research efforts into MARL have
dealt with agent non-homogeneity, scalability, decentralized learning, and
non-stationarity [9]. The difference between our work and MARL is that we
consider a centralized third-party entity who aims to _control_ the agents’
learning processes to change the resulting group behavior. There are, in
essence, two levels of decision-making: each agent chooses actions to
accomplish the agent’s goal, and the controller influences the agents by
making certain actions seem “better” and thus more likely to be chosen. The
goal of the third-party controller may be aligned with, or completely
different from the goals of the agents.

Consider a traffic control example. Drivers query tools such as Google Maps to
get the fastest routes, but as a central controller Google Maps could optimize
the collective travel time of all their users. As an adversarial example, the
navigation app Waze collects crowd-sourced information on road blockages and
police presence. Reports have accused angry homeowners of reporting false
blockages to reduce traffic on neighborhood streets [10], and have accused
reports of false police vehicles of reducing the integrity of the app’s
functions [11]. No matter the outcome, these are examples of the two levels of
learning: drivers follow the navigation advice to get to their destinations
quickly, and third-parties try to change how drivers accomplish these goals.

###  1.2 Factored MDPs

For a MAS, ideas may be borrowed from game theory to define the MDP state as
the joint action of the agents. This formulation works best when the
controller is concerned with a configuration across all the agents; however,
this will suffer in dimensionality as the size of the state space grows
exponentially with respect to the size of the system. Techniques to handle the
enlarged state space include the factored MDP [12] or transition-independent
MDPs (TI-MDP) [13], in which state transition probabilities may be factored
into independent components, such as one per agent. For example, consider from
competitive game theory the best response dynamics, whereby an agent chooses a
new action that would have been optimal at the last game instance. The state-
to-state transition is the composition of the changes for each agent, and is
thus factorable. Solutions for this formulation include approximate policy
iteration [14], graphical methods [15], as well as approximate transition
independence [16]. Efforts to reduce the scope of policy search include
efficient policy sampling methods [17], relaxations to deterministic policies
[18], and hierarchical methods [19].

Investigations into factored solutions exploit the structure of the MDPs. A
significant focus is on the exponentially expanded state space, where methods
for value function approximation are enabled by the independencies within the
state transitions [20], [21]. As large state spaces are generally the limiting
factor for computation, most study has concentrated on handling the state
space, leaving much less focus on efficient methods for large policy spaces.
In applications like MAS, however, complex policy spaces can lead to
prohibitive searching time in the optimization step of methods like value
iteration (VI) and policy iteration (PI). We proposed an approach for large
policy spaces in a previous work [22], where the action space is structured
such that agents are assigned to clusters, i.e. factors, where each cluster
can receive a different action. Imbuing this structure into the policy space
enables focused methods for approximate policy optimization.

###  1.3 Clustering

In this work we come to focus on clustered control techniques for MAS.
Clustering techniques [23] are of importance in many engineering fields such
as wireless sensor networks [24] [25], and in particular, clustering for the
purpose of control [26]. Robotic swarms provide a rich domain for application,
where algorithms commonly aim to mimic animals’ innate abilities for self-
grouping [27] [28]. Clustering in social media presents new challenges for
analysis; the unpredictability of the users has led to data-driven techniques
in machine learning [29].

Clustering has been extensively studied in the machine learning literature,
such as in nearest neighbor search algorithms for unsupervised classification.
Here we emphasize that we take an agent or node-based view of the MAS rather
than an edge-based focus such as [30]. The set of agents is assumed to be
partitioned, such that agents in the same partition receive the same control
from central command, yet different clusters may receive different controls.
The intuition is twofold: first, heterogeneous agents may still fall into a
fewer number of similar types, and a practitioner may want to personalize
controls for each type in accordance to system goals and constraints.
Secondly, more degrees of freedom in control can yield better outcomes, even
amongst agents for whom no clear partitions exist. Introducing some
flexibility in the controls can improve performance of the outcome, as we show
in section 2.2. The question stands as how to optimally choose the set
partitions for the control objective. The TI-MDP MAS setup differs in that the
objective does not necessarily care about closeness of the agents; the
objective is concerned with the resulting value achieved by a cluster
configuration. Our focus turns to the study of optimization of set partitions.

While the general optimization problem is known to be NP hard, approximations
have been studied across many applications. Variants of this setup have been
studied in the multiway partition problem (MPP) [31], but these are generally
concerned with minimization with non-negativity constraints preventing
analysis of maximization problems. Equivalently, the problem may be stated as
an objective subject to a matroid constraint, for which a celebrated $1/2$
approximate algorithm [32] for submodular optimization was then improved to a
$(1-1/e)$ approximation in [33] [34].

###  1.4 Our Contributions

In this work study the _cluster-based factored MDP control problem_ , both in
terms of policy and the clustering assignment. We proceed with the TI-MDP
approach for a MAS, and show that introducing degrees of freedom into the
policy with a factored control yields a better optimal value. This
formulation, however, is found to complicate finding an optimal policy due to
the high dimensionality of the new action space. This motivates the main
results; we introduce Clustered Value Iteration (CVI), an approximate “round
robin” method for solving a MDP whose complexity is independent of the number
of clusters. Convergence properties of CVI are established, along with
complexity and error analyses. The next section explores a deep dive into
factored MDPs with cluster-additive reward functions; CVI is shown to find an
optimal policy for this class of problems.

The following section investigates the optimal clustering assignment problem
of the agents. While the full discrete optimization problem is NP-hard, we
show that the value function is submodular for certain types of MDPs, thus
allowing properties of submodularity to help find an approximate solution. We
offer an approximate approach that iteratively builds clusters through greedy
splitting. The clustering assignments found by this algorithm produce values
that form a submodular lower bound for values of optimal clustering
assignments.

##  2 Problem Statement

###  2.1 Multi Agent MDPs

Consider a multi-agent system modeled as a _Markov Decision Process_ (MDP)
$\mathcal{M}=(\mathcal{S},\mathcal{A},R,T,\gamma)$ consisting of: the state
space of the system $\mathcal{S}$, the action space of the system
$\mathcal{A}$, a reward function
$R:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$, a probabilistic state
transition function
$T:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to\mathbb{R}$, and a discount
parameter $\gamma\in(0,1)$.

The MDP must next be related to the MAS. Consider a system of $0<N<\infty$
possibly heterogeneous agents, denoted as the set $\mathcal{N}$. At any time
$t$, each agent $n\in\mathcal{N}$ executes an action from some finite set of
options $S_{n}$, i.e. from the set of _substates_ available to $n$. The
resulting joint action across the agents $s=\\{s_{1},\dots,s_{N}\\}$ fully
describes the system and is therefore defined as the _state_. The state space
is thus $\mathcal{S}=\bigotimes_{n\in\mathcal{N}}S_{n}$. In general, a state
written with a set subscript such as $s_{\mathcal{B}}$ refers to the actions
realized in state $s$ by the agents in $\mathcal{B}$, i.e.
$s_{\mathcal{B}}=\\{s_{b}|b\in\mathcal{B}\\}$.

The agents’ decision making processes are assumed to depend on both the
current state $s$ and the influence control $\alpha\in\mathcal{A}$. This
process could be defined through tools like game theory, or it may be learned
from observation. Given a state-action pair, the _state transition function_
defines the transition probability to a new state in the form
$T(s,\alpha,s^{\prime})=p(s^{\prime}|s,\alpha)$. The controller selects
actions to encourage the agents to often be in “good” states and to avoid
“bad” states. This knowledge of good and bad is encoded in the _reward
function_ , which maps state-action pairs to a scalar reward. In this
formulation it is assumed the reward function is deterministic as it encodes
the controller’s known objective.

The superplayer controls the system by exerting a policy
$\pi:\mathcal{S}\to\mathcal{A}$. The goodness of a policy is evaluated via its
expected (infinite horizon) discounted sum of rewards, known as the _value
function_ :

$V^{\pi}(s)=\mathbb{E}^{\pi}\left[\sum_{k=1}^{\infty}\gamma^{k}r(s_{k},\alpha_{k})\right].$
(1)

An optimal policy $\pi^{*}$ is one that maximizes the value function,

$\pi^{*}(s)\in\operatorname*{arg\,max}_{\pi}V^{\pi}(s).$ (2)

For brevity, the corresponding optimal value will be denoted as $V^{*}(s)$.
The notation $V\in\mathbb{R}^{|\mathcal{S}|}$ will refer to the vector of
values $V(s)\ \forall\ s\in\mathcal{S}$.

The optimal value is known to be unique, and there exists an optimal
stationary policy that only considers the current state [35]. The optimal
value function will also satisfy the Bellman equation.

###### Definition 1

The _Bellman operator_ $\mathbf{T}$ applied to the value function $V(s)$ is,

$\displaystyle\mathbf{T}V(s)$
$\displaystyle=\max_{\alpha}\mathbb{E}_{s^{\prime}|s,\alpha}\left[r(s,\alpha)+\gamma
V(s^{\prime})\right],$ (3)
$\displaystyle=\max_{\alpha}\sum_{s^{\prime}}p(s^{\prime}|s,\alpha)(r(s,\alpha)+\gamma
V(s^{\prime})).$ (4)

The optimal value function satisfies,

$\mathbf{T}V^{*}(s)=V^{*}(s).$ (5)

###  2.2 Cluster-Based Control

An immediate refinement of the MDP setup is that a better optimal value is
attainable by increasing the degrees of freedom for the control. This is
constructed with the _clustered formulation_ , in which the agents are
partitioned into $C$ clusters and controls are transmitted to each cluster. A
_clustering assignment_ of the agents is the set of sets
$\mathcal{C}=\\{c_{1},\dots,c_{C}\\}$ such that $c_{u}\cap c_{v}=\emptyset\
\forall u,v\in[1,C],u\neq v$ and $\cup_{c\in\mathcal{C}}=\mathcal{N}$.

In this setup, the action is expanded from the scalar $\alpha$ to the vector
$\bm{\alpha}=[\alpha_{1},\dots,\alpha_{C}]$ with action space
$\mathcal{A}=\bigotimes_{n\in\mathcal{N}}A_{c}$ where $\alpha_{c}\in A_{c}$.
By design, the agents in some cluster $c$ only see the action assigned to
their cluster, $\alpha_{c}$. For ease of notation, the action seen by agent
$n$ will be denoted by $\bm{\alpha}_{n}$ instead of $\bm{\alpha}_{c(n)}$. The
policy is likewise expanded to the tuple $\Pi=\\{\pi_{1},\dots,\pi_{C}\\}$
where $\Pi(s)\in\mathcal{A}$.

The rest of this paper will focus on a special type of MDP that lends itself
to the clustered control policy.

###### Definition 2

A _transition independent MDP_ (TI-MDP) or _factored MDP_ is a MDP whose state
transition probabilities may be expressed as the product of independent
transition probabilities,

$\displaystyle
p(s^{\prime}|s,\bm{\alpha})=\prod_{i\in\mathcal{I}}p(s_{i}^{\prime}|s,\bm{\alpha}_{i}).$

The TI-MDP is “agent-independent” if $\mathcal{I}$ is equivalent to the set of
agents, and “cluster-independent” if $\mathcal{I}$ is equivalent to the set of
clusters. Note that independent transitions across the agents implies
independent transitions across the clusters,

$\displaystyle
p(s^{\prime}|s,\bm{\alpha})=\prod_{c\in\mathcal{C}}p(s_{c}^{\prime}|s,\alpha_{c}).$

Definition 2 describes multi-agent systems where each agent makes their
decision independently after observing the current state and control. This
includes general non-cooperative games, for example, those with best response
style dynamics [3]. In best response style game-play, each player $n$ chooses
an action that maximizes their utility function $u$ based on the last round of
game-play, i.e.
$s_{n}^{\prime}\in\operatorname*{arg\,max}u(s,\bm{\alpha}_{n},s_{n}^{\prime})$.
Knowledge of the players’ utilities allows the controller to model each
agent’s decision process as a probability function
$p(s_{n}^{\prime}|s,\bm{\alpha}_{n})$. Therefore, any overall state transition
$s\to s^{\prime}$ can be described as the product of $N$ independent factors
that are each conditioned on $s$ and $\bm{\alpha}$. In comparison,
communication between agents after observing $(s,\bm{\alpha})$ and before
setting a probability distribution over $s_{n}^{\prime}$ may introduce
dependence between agents; however, disjoint communication sets may still
enable transition independence between clusters.

Recall the second motivation for clustering agents: more degrees of freedom in
control implies improved performance. This idea is formalized in the following
lemma.

###### Lemma 1

Consider a TI-MDP whose agents have been partitioned into $C$ clusters of
arbitrary agent assignment. The optimal values achieved from $C=1$ and $C=N$
are the lower and upper bounds on the optimal values achieved by arbitrary
$C$.

$V^{*}_{C=1}(s)\leq V^{*}_{1<C<N}(s)\leq V^{*}_{C=N}(s).$ (6)

#### Proof:

See [22]. $\square$

This initial result shows that any arbitrary clustering assignment can improve
the optimal value of the MDP. This finding motivates further investigation
into the clustered formulation, namely to find good clustered control
policies, to characterize the benefit of such policies, and to find optimal
clustering assignments.

##  3 CVI

The main goal is to attain the improved value enabled by the clustered-based
control, but this necessitates a good control policy. Cluster-based control
$\bm{\alpha}$ introduces more degrees of freedom than scalar $\alpha$, but
this method suffers in computation time. As standard techniques like VI and PI
search over the entire action space, and as the clustered policy increases the
number of actions dramatically, the standard Bellman update becomes
intractable. Say the controller defines $C$ clusters, where $|A_{c}|=M$; then
the control $\bm{\alpha}$ has $|\mathcal{A}|=M^{C}$ possible options. PI has a
complexity of $O(|\mathcal{A}||\mathcal{S}|^{2}+|\mathcal{S}|^{3})$ per
iteration, and VI a complexity of $O(|\mathcal{A}||\mathcal{S}|^{2})$ per
iteration [36]. This causes the computation time for either method to grow
exponentially with the number of clusters. The conclusion is that an alternate
method for solving for $\pi^{*}$ is needed.

The solution presented in this work is called Clustered Value Iteration (CVI)
as shown in Algorithm 1. This algorithm is similar to standard VI, but differs
in that the optimization takes “round-robin” approach across the clusters. At
each iteration, the algorithm improves the control for one cluster at a time.
The policies across the other clusters are held constant until their turn to
be optimized in a future iteration. The intuition is that the controller can
focus on making improvements cluster-by-cluster, and perform policy
improvement without iterating over the whole action space.

This investigation into clustered systems is thematically related to state
aggregation methods, but the technical formulations are distinct. Both methods
aim to reduce the dimensionality of the problem by solving smaller but related
MDPs. In a state aggregation method, similar states are grouped together to
form a new system with a reduced state space. In comparison, the clustered
formulation is designed for MDPs whose state space is the Cartesian product
across a set of substates; the clustering assignment partitions the substates,
resulting in Cartesian products of a smaller size. In aggregate methods the
new transition matrix is a weighted sum of the original transition
probabilities; in the clustered formulation, the transitions are decomposed by
their factored structure. These two methods could be used in tandem to enjoy
further dimensionality reduction, whereby a clustered formulation could use
aggregation techniques on the set of substates.

###  3.1 Algorithm Statement

Before explaining the algorithm, the following notation is introduced.

There exists an optimal deterministic policy for this MDP, so our focus is
constrained to deterministic policies $\Pi$. Let
$\pi_{c}^{k}(s)=\alpha_{c}^{k}$ denote the action to cluster $c$ at iteration
$k$ for state $s$. The vector across all clusters is
$\Pi^{k}(s)=\bm{\alpha}^{k}$. With some new notation, the Bellman operator can
be defined with respect to one element of $\bm{\alpha}$.

###### Definition 3

Let $\Pi_{\setminus c}(s)=\bm{\alpha}_{\setminus c}$ be the tuple of $\alpha$
without the element specified by the subscript.

$\displaystyle\Pi_{\setminus c}(s)$
$\displaystyle\triangleq\\{\pi_{1}(s),\dots,\pi_{c-1}(s),\pi_{c+1}(s),\dots,\pi_{C}(s)\\},$
(7) $\displaystyle\bm{\alpha}_{\setminus c}$
$\displaystyle\triangleq\\{\alpha_{1},\dots,\alpha_{c-1},\alpha_{c+1},\dots,\alpha_{C}\\}.$
(8)

###### Definition 4

Let $\mathbf{T}^{c}_{\Pi}$ be the _clustered Bellman operator_ that maximizes
with respect to $\alpha_{c}$ for fixed $\Pi_{\setminus c}(s)$.

$\displaystyle\mathbf{T}^{c}_{\Pi}V(s)\triangleq\max_{\alpha_{c}}\mathbb{E}_{s^{\prime}|s,\bm{\alpha}}[r(s,\bm{\alpha})+\gamma
V(s^{\prime})],$
$\displaystyle=\max_{\alpha_{c}}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\Pi_{\setminus
c}(s),\alpha_{c}\\})(r(s,\\{\Pi_{\setminus c}(s),\alpha_{c}\\})+\gamma
V(s^{\prime})).$ (9)

With this notation, a solution for finding a cluster-based control policy can
now be presented. To enable the round-robin optimization, the order of the
cluster optimization must be defined. It will generally be assumed in this
paper that the following statement holds.

###### Assumption 1

The cluster optimization order $\Omega=\\{c_{k}\\}_{k\geq 0}$ is chosen such
that as $k\to\infty$, each cluster is chosen infinitely often.

This assumption can be trivially fulfilled by rotating between all the
answers. The second assumption made in this paper is that the reward function
satisfies the following properties:

###### Assumption 2

The reward function is non-negative and bounded for all $s\in\mathcal{S}$,
$\bm{\alpha}\in\mathcal{A}$.

The proposed algorithm begins like standard VI by initializing the value of
each state to zero. For each following iteration $k$, the algorithm selects a
cluster according to the optimization order $c_{k}\leftarrow\Omega(k)$. Next,
the clustered Bellman operator $\mathbf{T}_{\Pi^{k}}^{c_{k}}$ is applied to
the current value estimate $V_{k}(s)$. In the clustered Bellman operator, all
clusters except for $c_{k}$ follow the fixed policy $\Pi^{k}_{\setminus
c_{k}}$, while the action for $c_{k}$ is optimized. The policy for $c_{k}$ is
updated accordingly. A tie-breaking rule for actions is assumed for when
$\operatorname*{arg\,max}\mathbf{T}_{\Pi^{k}}^{c_{k}}V_{k}(s)$ has more than
one element, such as choosing the $\alpha_{c_{k}}$ with the smallest index.
The algorithm terminates when the difference in value update is appropriately
small.

$V_{0}(s)\leftarrow 0,\ \forall s\in\mathcal{S}$;

Initialize policy guess
$\Pi^{0}(s)=\\{\pi_{1}^{0}(s),\dots,\pi_{C}^{0}(s)\\},\forall
s\in\mathcal{S}$;

Choose cluster optimization order $\Omega$;

$k=-1$;

while  _$\|V_{k}-V_{k-1}\|_{\infty} >\epsilon$_ do

$k=k+1$;

$c_{k}\leftarrow\Omega(k)$;

$V_{k+1}(s)\leftarrow\mathbf{T}^{c_{k}}_{\Pi^{k}}V_{k}(s),\ \forall
s\in\mathcal{S}$;

$\pi_{c_{k}}^{k+1}(s)\leftarrow\operatorname*{arg\,max}_{\alpha_{c_{k}}}\mathbf{T}^{c_{k}}_{\Pi^{k}}V_{k}(s),\
\forall s\in\mathcal{S}$;

$\Pi_{\setminus c_{k}}^{k+1}(s)\leftarrow\Pi_{\setminus c_{k}}^{k}(s)$;

end while

Algorithm 1 Clustered Value Iteration (CVI)

The cluster-based approach of CVI improves computation complexity as the
optimization step searches over a significantly smaller space. Again, let each
$\alpha_{c}$ have $M$ possible actions. Standard VI on cluster-based controls
has a complexity of $O(M^{C}|\mathcal{S}|^{2})$ per iteration; in comparison,
CVI iterations have a complexity of $O(M|\mathcal{S}|^{2})$, thus eliminating
the per-iteration dependence on the number of clusters. While there will be an
increase in the number of clusters, the savings per iteration will make up for
the overall computation time as explored in simulation in Section 6.

The following sections will examine the computation of this algorithm, develop
its convergence properties, and discuss the optimality of the found policy.

###  3.2 Convergence

This section studies the properties of the CVI algorithm. The first main
theorem below establishes convergence.

###### Theorem 1

Convergence of CVI. Consider the CVI Algorithm (Algorithm 1) for a MDP such
that Assumptions 1 and 2 are fulfilled. Then, there exists,
$\widehat{V}\in\mathbb{R}^{|\mathcal{S}|}$ such that
$V_{k}\rightarrow\widehat{V}$ as $k\rightarrow\infty$.

The following lemmas will be used to prove Theorem 1. The first result will
show boundedness of the value estimates.

###### Lemma 2

Boundedness of Values. The CVI iterates satisfy $\sup_{k\geq
0}\|V_{k}\|_{\infty}<\infty$.

#### Proof:

Let $r=\sup_{s}r(s,\bm{\alpha})$.

$\displaystyle V_{k+1}(s)$
$\displaystyle=\max_{\alpha_{c_{k}}}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\Pi^{k}_{\setminus
c_{k}}(s),\alpha_{c_{k}}\\})(r(s,\\{\Pi^{k}_{\setminus
c_{k}}(s),\alpha_{c_{k}}\\})+\gamma V_{k}(s^{\prime})),$ $\displaystyle\leq
r+\gamma\|V_{k}\|_{\infty}.$

Therefore $\|V_{k}\|_{\infty}\leq
r\sum_{i=0}^{k-1}\gamma^{i}+\gamma^{k}\|V_{0}\|_{\infty}$. As $\gamma<1$,
$\limsup_{k\to\infty}\|V_{k}\|_{\infty}\leq r/(1-\gamma)$. $\square$

###### Lemma 3

Monotonicity of the Clustered Bellman Operator. For each $\Pi(s)$ and
$s\in\mathcal{S}$ define
$\mathbf{T}_{\Pi}:\mathbb{R}^{|\mathcal{S}|}\to\mathbb{R}$ as,

$\displaystyle\mathbf{T}_{\Pi}V(s)=\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,\Pi(s))(r(s,\Pi(s))+\gamma
V(s^{\prime})).$ (10)

Then $\mathbf{T}_{\Pi}$ is monotone in the sense that if $V_{1}(s)\geq
V_{2}(s)$ then $\mathbf{T}_{\Pi}V_{1}(s)\geq\mathbf{T}_{\Pi}V_{2}(s)$.

#### Proof:

Note that the action here is fixed. Result follows from [35] Volume II, Lemma
1.1.1. $\square$

Now we proceed with the proof of Theorem 1.

#### Proof:

First, induction will show that the sequence $\\{V_{k}(s)\\}_{k\geq 0}$
increases monotonically for all $s$. The base case inequality $V_{0}(s)\leq
V_{1}(s)$ will shown first. The estimated values are initialized to
$V_{0}(s)=0$. The next value is evaluated as
$V_{1}(s)=\max_{\alpha_{c_{0}}}\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,\\{\Pi^{0}_{\setminus{c_{0}}}(s),\alpha_{c_{0}}\\})(r(s,\\{\Pi^{0}_{\setminus{c_{0}}}(s),\alpha_{c_{0}}\\})+\gamma
V_{0}(s^{\prime}))=\max_{\alpha_{c_{0}}}r(s,\\{\Pi^{0}_{\setminus{c_{0}}}(s),\alpha_{c_{0}}\\})\geq
V_{0}(s)$, thus holding the conclusion for any $c$ and $s$.

Next we will show that $V_{k+1}(s)\geq V_{k}(s)$. Note that preforming the
optimization $\mathbf{T}_{\Pi_{k}}^{c_{k}}V_{k}(s)=V_{k+1}(s)$ yields new
action $\bm{\alpha}_{k+1}$ for $s$. Letting $\Pi^{k+1}=\bm{\alpha}_{k_{1}}$ in
Eq (10) means that $\mathbf{T}_{\Pi^{k+1}}V_{k}(s)=V_{k+1}(s)$.

Consider $V_{k+1}(s)=\mathbf{T}_{\Pi^{k}}^{c_{k}}V_{k}(s)$ with action
maximizer $\alpha_{c_{k}}^{k+1}$ for $s$. If
$\alpha_{c_{k}}^{k+1}=\alpha_{c_{k}}^{k}$, then this implies that
$\bm{\alpha}^{k+1}=\bm{\alpha}^{k}$ and
$V_{k+1}(s)=\mathbf{T}_{\Pi^{k}}V_{k}(s)$. Since
$V_{k}(s)=\mathbf{T}_{\Pi^{k}}V_{k-1}(s)$, then by Lemma 3
$\mathbf{T}_{\Pi^{k}}V_{k}(s)\geq\mathbf{T}_{\Pi^{k}}V_{k-1}(s)$ for
$V_{k}(s)\geq V_{k-1}(s)$ for all $s$.

However if $\alpha_{c_{k}}^{k+1}\neq\alpha_{c_{k}}^{k}$, then the value can be
bounded:

$\displaystyle
V_{k+1}(s)=\mathbf{T}_{\Pi^{k+1}}V_{k}(s)=\mathbf{T}_{\Pi^{k}}^{c_{k}}V_{k}(s),$
$\displaystyle=\max_{\alpha_{c_{k}}}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\Pi_{\setminus{c_{k}}}^{k}(s),\alpha_{c_{k}}\\})(r(s,\\{\Pi_{\setminus{c_{k}}}^{k}(s),\alpha_{c_{k}}\\})+\gamma
V_{k}(s^{\prime})),$
$\displaystyle>\sum_{s^{\prime}}p(s^{\prime}|s,\Pi^{k}(s))(r(s,\Pi^{k}(s))+\gamma
V_{k}(s^{\prime}))=\mathbf{T}_{\Pi^{k}}V_{k}(s).$

Since $\mathbf{T}_{\Pi^{k}}V_{k}(s)\geq\mathbf{T}_{\Pi^{k}}V_{k-1}(s)$, then
$\mathbf{T}_{\Pi^{k+1}}V_{k}(s)\geq\mathbf{T}_{\Pi^{k}}V_{k-1}(s)$ for all
$s$.

By the boundedness property established by Lemma 2 and the above monotonicity
of the sequence $\\{V_{k}(s)\\}_{k\geq 0}$, for all $s\in\mathcal{S}$, we
conclude the convergence of $\\{V_{k}\\}$. $\square$

###### Lemma 4

Contraction. The clustered Bellman operator is a contraction for fixed $\Pi$,
$c$,

$\displaystyle\|\mathbf{T}^{c}_{\Pi}V_{1}-\mathbf{T}^{c}_{\Pi}V_{2}\|\leq\gamma\|V_{1}-V_{2}\|.$
(11)

#### Proof:

Note that $\mathbf{T}_{\Pi}^{c}$ is the same operator applied to both $V_{1}$,
$V_{2}$. The result holds. $\square$

With this convergence property established, it is clear that the CVI Algorithm
may be used to find a usable control policy. In the next section, the
performance of the found policy will be investigated.

###  3.3 Error Analysis

Note that while Theorem 1 establishes convergence of CVI, it does not
establish the uniqueness of the achieved fixed point. In fact, this fixed
point will depend on the initial action guess and the cluster optimization
order. This section will describe the performance of any fixed point of the
algorithm.

###### Theorem 2

Consistency. The true optimal value $V^{*}$ is a fixed point of
$\mathbf{T}_{\Pi^{*}}^{c}$ for any $c$.

#### Proof:

Let $\Pi^{*}(s)=\bm{\alpha}^{*}$ and $V^{*}(s)$ be a true optimal policy,
optimal control for $s$, and optimal value of $s$ for $M$. Now consider one
iteration of CVI that optimizes with respect to cluster $c$. The next choice
of $\alpha_{c}$ is
$\alpha_{c}^{\prime}=\operatorname*{arg\,max}_{\alpha_{c}}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\Pi_{\setminus
c}^{*}(s),\alpha_{c}\\})(r(s,\bm{\alpha})+\gamma V^{*}(s))$. If
$\alpha_{c}^{\prime}\neq\alpha_{c}^{*}$, then the choice
$\bm{\alpha}^{\prime}=\\{\alpha_{1}^{*},\dots,\alpha_{c}^{\prime},\dots,\alpha_{c}^{*}\\}$
would yield a higher value than
$\bm{\alpha}^{*}=\\{\alpha_{1}^{*},\dots,\alpha_{c}^{*},\dots,\alpha_{c}^{*}\\}$.
Therefore $\Pi^{*}(s)=\bm{\alpha}^{*}$ is not a true optimal policy and
control. This contradicts the assumption that $V^{*}(s)$ is the optimal value
and that $\Pi^{*}(s)=\bm{\alpha}^{*}$ are optimal policies and controls. This
means that $\mathbf{T}_{\Pi^{*}}^{c}V^{*}(s)=V^{*}(s)$. $\square$

Now, consider the performance of any candidate policy $\Pi$.

###### Theorem 3

Suboptimiality of a Policy. Let $V^{*}$ be the true optimal value of a MDP
under optimal policy $\pi^{*}$, and let $\mathbf{T}^{*}V$ refer to the
application of the true Bellman operator. Then,

$\displaystyle\text{(UB)}\
\|V^{*}-\widehat{V}\|\leq\frac{1}{1-\gamma}\|\widehat{V}-\mathbf{T}^{*}\widehat{V}\|,$
(12) $\displaystyle\text{(LB)}\
\|V^{*}-\widehat{V}\|\geq\frac{1}{1+\gamma}\|\widehat{V}-\mathbf{T}^{*}\widehat{V}\|.$
(13)

#### Proof:

$\displaystyle\|V^{*}-\widehat{V}\|_{\infty}$
$\displaystyle=\|V^{*}-\mathbf{T}^{*}\widehat{V}+\mathbf{T}^{*}\widehat{V}-\widehat{V}\|_{\infty}$
$\displaystyle\leq\|\mathbf{T}^{*}V^{*}-\mathbf{T}^{*}\widehat{V}\|_{\infty}+\|\mathbf{T}^{*}\widehat{V}-\widehat{V}\|_{\infty}$
$\displaystyle\leq\gamma\|V^{*}-\widehat{V}\|_{\infty}+\|\mathbf{T}^{*}\widehat{V}-\widehat{V}\|_{\infty}$
$\displaystyle\Rightarrow(1-\gamma)\|V^{*}-\widehat{V}\|_{\infty}\leq\|\mathbf{T}^{*}\widehat{V}-\widehat{V}\|_{\infty}$
$\displaystyle\Rightarrow\|V^{*}-\widehat{V}\|_{\infty}\leq\frac{1}{1-\gamma}\|\mathbf{T}^{*}\widehat{V}-\widehat{V}\|_{\infty}$
$\displaystyle\|\widehat{V}-V^{*}\|_{\infty}$
$\displaystyle=\|\widehat{V}-\mathbf{T}^{*}\widehat{V}+\mathbf{T}^{*}\widehat{V}-V^{*}\|_{\infty}$
$\displaystyle\geq\|\widehat{V}-\mathbf{T}^{*}\widehat{V}\|_{\infty}-\|\mathbf{T}^{*}\widehat{V}-\mathbf{T}^{*}V^{*}\|_{\infty}$
$\displaystyle\geq\|\widehat{V}-\mathbf{T}^{*}\widehat{V}\|_{\infty}-\gamma\|\widehat{V}-V^{*}\|_{\infty}$
$\displaystyle\Rightarrow(1+\gamma)\|V^{*}-\widehat{V}\|_{\infty}\geq\|\mathbf{T}^{*}\widehat{V}-\widehat{V}\|_{\infty}$
$\displaystyle\Rightarrow\|V^{*}-\widehat{V}\|_{\infty}\geq\frac{1}{1+\gamma}\|\mathbf{T}^{*}\widehat{V}-\widehat{V}\|_{\infty}$

$\square$

The right hand side of equations (12), (13) depend on the term
$\|\widehat{V}-\mathbf{T}^{*}\widehat{V}\|$ which is a measure of the possible
improvement under the full Bellman operator. Upon reaching a fixed point of
CVI, a practitioner can either perform one evaluation of the full Bellman
operator to check the bound, or use the fixed point of CVI as an initial guess
for standard VI.

The structures of (12) (13) imply that a hybrid approach of combining CVI and
VI style updates may be used to find optimal $V^{*}$. This idea will be
further explored in the next section.

###  3.4 Hybrid Approach

The structures of (12) (13) imply that a hybrid approach of combining CVI and
VI style updates may be used to find optimal $V^{*}$. The error introduced by
the computationally cheap CVI updates may be rectified with an occasional
expensive VI update. From any value guess $V_{k}$, CVI updates are used to
compute $\widehat{V}_{k+1}$, where the stopping criterion may be convergence
to a fixed point, an approximate fixed point, or a set number of updates. As
the policy found by CVI may be a local optimum, the subsequent VI update
corrects the policy guess, thus enabling the next iteration to begin with a
fresh policy initialization.

###### Theorem 4

Convergence and Optimality of Hybrid CVI/VI. Consider the CVI Algorithm with
periodic VI updates. Let the reward function be non-negative and bounded for
all $s\in\mathcal{S}$. Then $V_{k}\to V^{*}$ as $k\to\infty$.

#### Proof:

Convergence may once again be shown through monotonicity and boundedness of
updates. $V_{k}(s)\leq\widehat{V}_{k+1}(s)$ for all $s\in\mathcal{S}$ is
already known for CVI updates. The next improvement $\widehat{V}_{k+1}(s)\leq
V_{k+1}(s)$ for all $s\in\mathcal{S}$ may be determined as the $\mathbf{T}$
operator searches over the entire action space and will perform at least as
well as a CVI update.

To see optimality, note that for any evaluation
$\mathbf{T}\widehat{V}_{k}(s)=V_{k}(s)$, if $\widehat{V}_{k}(s)=V_{k}(s)$ then
the fixed point $V_{k}(s)=V^{*}(s)$ of $\mathbf{T}$ has been achieved; else
there will be monotonic improvement $V_{k}(s)\geq\widehat{V}_{k}(s)$. As
$V^{*}(s)\geq\widehat{V}_{k}$ for all $k$ (due to $r(s,\bm{\alpha})\geq 0$ and
$V_{0}(s)=0$), $V_{k}(s)\to V^{*}(s)$ as $k\to\infty$. $\square$

###  3.5 Extensions & Variants

Bellman updates may be substituted with the clustered updates in a variety of
dynamic programming approaches and variants. The general takeaway is that the
clustered Bellman operator may be used in lieu of the full maximization in
general dynamic programming techniques. Occasional VI updates may still be
desirable to ensure optimal convergence, so a balance may set to achieve fast,
accurate performance.

#### Value Function Approximation (VFA)

Recall that CVI was motivated to handle the expansion of the action space of
the system. This may be combined with existing techniques to handle the
combinatorial nature of the agent-based formulation.

Consider the VFA approach [35], which approximates the value function via some
parametric class, such as a linear basis function. The value function may be
approximated as $\overline{V}=\Phi\theta$, where the parameter vector may be
obtained by considering the fixed point $\Phi\theta=\Pi\mathbf{T}(\Phi\theta)$
where $\Pi$ is the projection operator.

For a selected VFA construction, CVI-style updates (9) may be used for the
application of the Bellman operator. The resulting error between the fixed
point $\widehat{\overline{V}}$ after both VFA and CVI and the optimal point
after VFA $\overline{V}^{*}$ may be analyzed as,

$\displaystyle\|\overline{V}^{*}-\widehat{\overline{V}}\|\leq\|\overline{V}^{*}-V^{*}\|+\|V^{*}-\widehat{V}\|+\|\widehat{V}-\widehat{\overline{V}}\|.$
(14)

Note that the three terms in equation (14) may be interpreted as the combined
error from VFA and CVI. Terms 1 and 3 are the error from the projection
operator, and term 2 may be found from (12). The resulting algorithm will
preserve the computational savings from both VFA and CVI.

#### Clustered Policy Iteration

The PI algorithm may also make use of CVI updates to reduce computation in the
policy improvement step. While monotonicity will still give convergence, the
computation savings may not be significant. Recall that the per-iteration
complexity of PI is $O(|\mathcal{A}||\mathcal{S}|^{2}+|\mathcal{S}|^{3})$; the
computation here will likely be dominated by the matrix inversion term
$|\mathcal{S}|^{3}$, meaning that the clustered Bellman operator may be used,
but may not be the most impactful step for speed.

#### Approximate PI (API)

In practice, API [35] is often used in lieu of PI or VI. Rather than
alternating between full policy evaluation and full policy improvement, API
only computes these steps up to some allowed error bounds.

The results of Theorem 3 are similar to those developed for API as both
techniques perform an approximate policy improvement step. The difference is
that API has an additional step of approximately evaluating each proposed
policy with $V_{k}\approx V_{\pi_{k}}$. In CVI, policy evaluation is only
performed after the found policy converges. The two techniques are similar in
concept, but CVI is designed specifically for structure inherent to a cluster-
based control policy.

The policy improvement step of API can be modified to be the cluster-wise
maximization as in CVI. This means that API policy improvement bound
$\|\mathbf{T}_{\Pi^{k}}V_{k}-\mathbf{T}V^{*}\|\leq\epsilon$ measures the
goodness of the maximization approximation in CVI.

#### Asynchronous Methods

General VI may be adapted such that value updates across the states are
performed asynchronously. These techniques generally yield faster convergence
and enable parallel computation. In particular, the Gauss-Seidel method is an
adaptation of VI whereby the value for only one state is updated at each
iteration. CVI-style updates may be directly used in conjunction with an
asynchronous method. The clustered structure lends itself to distributed
computation, as the optimization step across each entry $\alpha_{c}$ may be
performed by a different machine.

##  4 Separable Systems

The next focus of this paper will be on a special class of TI-MDPs that
satisfy an additional structural property. This class is of particular
interest because the extra structure enables the CVI algorithm to find optimal
policies.

###### Definition 5

The TI-MDP is called a _separable_ system if the rewards are additive with
respect to the cluster assignments:

$r(s,\bm{\alpha})=\sum_{c\in\mathcal{C}}r(s_{c},\alpha_{c})=\sum_{c\in\mathcal{C}}r_{c}.$
(15)

A more general version of this definition is additive rewards with respect to
the agents, i.e. $r(s,\bm{\alpha})=\sum_{n}r(s_{n},\bm{\alpha}_{n})$. Note
that rewards separable by agent are also separable by cluster. The rest of
this section will presuppose that the system of interest can be modeled as a
separable TI-MDP.

This category of MDPs occurs naturally arises in clustered control
applications. For example, agents may fall into a customer type, and the
central planner may define a reward based on the type. The reward per cluster
may be the number of agents showing desirable behavior, i.e.
$r(s_{c},\alpha_{c})=\sum_{n\in c}\mathbbm{1}(s_{n}\in\mathcal{D}_{c})$ where
$\mathcal{D}_{c}$ is a set of desirable actions for agents of type $c$. If the
agent types are not apparent _a priori_ , the reward may represent the
proportion of agents representing general good behavior, i.e.
$r(s,\bm{\alpha})=\frac{1}{N}\sum_{n}\mathbbm{1}(s_{n}\in\mathcal{D}_{n})$.
This structure further lends itself to a distributed setting, where a full
state need not be known to assign an agent reward.

Reward functions that are not separable depend on the whole state. For
example, zero-sum games and common toy non-cooperative games such as the
prisoner’s dilemma and chicken cannot be represented as separable TI-MDPs.
Rewarding desirable states, i.e.
$r(s,\bm{\alpha})=\mathbbm{1}(s\in\mathcal{D})$, will not be separable for
arbitrary $\mathcal{D}$; however, structured $\mathcal{D}$ as previously
described may be separable.

The next results discuss the performance of CVI on this special class of TI-
MDPs. The first finding asserts that value functions of separable TI-MDPs are
themselves separable.

###### Lemma 5

Separability of Bellman Operator on Separable Systems. Consider a separable
TI-MDP. For any VI evaluation, the full Bellman operator may be decomposed as
the sum of $C$ CVI updates:

$\displaystyle\mathbf{T}V_{k}(s)$
$\displaystyle=\sum_{c}\mathbf{T}^{c}V_{k}^{c}(s),$ (16)
$\displaystyle=\sum_{c}\max_{\alpha_{c}}\mathbb{E}_{s_{c}^{\prime}|s,\alpha_{c}}\left[r(s_{c},\alpha_{c})+\gamma
V_{k}^{c}(s^{\prime})\right].$ (17)

Furthermore for $V^{c}_{0}(s)=0$ then,

$\displaystyle V^{c}_{k+1}(s)$ $\displaystyle=\mathbf{T}^{c}V_{k}^{c}(s).$
(18)

#### Proof:

The proof will show by inductionthat each iteration of standard VI can be
split into independent evaluations over each cluster.

Base case. Initialize $V_{0}(s)=0$ for all $s$. Then
$V_{1}(s)=r(s,\bm{\alpha})$. Then,

$\displaystyle\mathbf{T}V_{2}(s)$
$\displaystyle=\max_{\bm{\alpha}}\sum_{s^{\prime}}p(s_{1}^{\prime}|s,\alpha_{1})\dots
p(s_{C}^{\prime}|s,\alpha_{C})\left[\sum_{c}r(s_{c},\alpha_{c})+\gamma
r(s^{\prime},\bm{\alpha}^{k=1})\right]$
$\displaystyle\begin{split}=&\max_{\bm{\alpha}}\Big{[}\sum_{s_{1}^{\prime}}p(s_{1}^{\prime}|s,\alpha_{1})\Big{[}\sum_{s_{2}^{\prime}}p(s_{2}^{\prime}|s,\alpha_{2})\Big{[}\dots\times\\\
&\sum_{s_{C}^{\prime}}p(s_{C}^{\prime}|s,\alpha_{C})\Big{[}\sum_{c}r(s_{c},\alpha_{c})+\gamma
r(s^{\prime},\bm{\alpha}^{k=1})\Big{]}\Big{]}\Big{]}\Big{]}\end{split}$
$\displaystyle=\max_{\bm{\alpha}}\mathbb{E}_{s_{1}^{\prime}|s,\alpha_{1}}\dots\mathbb{E}_{s_{C}^{\prime}|s,\alpha_{C}}\left[\sum_{c}r(s_{c},\alpha_{c})+\gamma
r(s^{\prime},\bm{\alpha}^{k=1})\right]$
$\displaystyle=\max_{\bm{\alpha}}\mathbb{E}_{s_{1}^{\prime}|s,\alpha_{1}}\dots\mathbb{E}_{s_{C}^{\prime}|s,\alpha_{C}}\left[\sum_{c}r(s_{c},\alpha_{c})+\gamma\sum_{c}r(s_{c}^{\prime},\alpha^{k=1}_{c})\right]$
$\displaystyle=\max_{\bm{\alpha}}\sum_{c}\left[\mathbb{E}_{s_{1}^{\prime}|s,\alpha_{1}}\dots\mathbb{E}_{s_{C}^{\prime}|s,\alpha_{C}}\left[r(s_{c},\alpha_{c})+\gamma
r(s_{c}^{\prime},\alpha^{k=1}_{c})\right]\right]$
$\displaystyle=\max_{\bm{\alpha}}\sum_{c}\mathbb{E}_{s_{c}^{\prime}|s,\alpha_{c}}\left[r(s_{c},\alpha_{c})+\gamma
r(s_{c}^{\prime},\alpha^{k=1}_{c})\right]$
$\displaystyle=\sum_{c}\max_{\alpha_{c}}\mathbb{E}_{s_{c}^{\prime}|s,\alpha_{c}}\left[r(s_{c},\alpha_{c})+\gamma
r(s_{c}^{\prime},\alpha^{k=1}_{c})\right]=\sum_{c}\mathbf{T}^{c}V_{2}^{c}(s)$

Notice that $r(s_{c}^{\prime})$ is independent of $s_{c^{\prime}}^{\prime}$
where $c^{\prime}\neq c$. The last line means that the resulting $V$ is
decomposable over $c$, and that each element of $\bm{\alpha}$ may be optimized
independently.

General case.

$\displaystyle\mathbf{T}V_{k}(s)$
$\displaystyle=\max_{\bm{\alpha}}\sum_{s^{\prime}}p(s_{1}^{\prime}|s,\alpha_{1})\dots
p(s_{C}^{\prime}|s,\alpha_{C})\left[\sum_{c}r(s_{c},\alpha_{c})+\gamma
V_{k}(s^{\prime})\right]$
$\displaystyle=\max_{\bm{\alpha}}\mathbb{E}_{s_{1}^{\prime}|s,\alpha_{1}}\dots\mathbb{E}_{s_{C}^{\prime}|s,\alpha_{C}}\left[\sum_{c}r(s_{c},\alpha_{c})+\gamma\sum_{c}V_{k}^{c}(s^{\prime})\right]$
$\displaystyle=\max_{\bm{\alpha}}\sum_{c}\mathbb{E}_{s_{1}^{\prime}|s,\alpha_{1}}\dots\mathbb{E}_{s_{C}^{\prime}|s,\alpha_{C}}\left[r(s_{c},\alpha_{c})+\gamma
V_{k}^{c}(s^{\prime})\right]$
$\displaystyle=\max_{\bm{\alpha}}\sum_{c}\mathbb{E}_{s_{c}^{\prime}|s,\alpha_{c}}\left[r(s_{c},\alpha_{c})+\gamma
V_{k}^{c}(s^{\prime})\right]$
$\displaystyle=\sum_{c}\max_{\alpha_{c}}\mathbb{E}_{s_{c}^{\prime}|s,\alpha_{c}}\left[r(s_{c},\alpha_{c})+\gamma
V_{k}^{c}(s^{\prime})\right]=\sum_{c}\mathbf{T}^{c}V_{k}^{c}(s)$

The last line shows that $V$ may again be decomposed for general $k$ and that
$\bm{\alpha}$ may be optimized over each element independently. Therefore,
each step of general VI may be expressed as $C$ CVI evaluations of the current
value. $\square$

Lemma 5 shows that each Bellman update may be written as a sum over clusters,
where each addend is only dependent on one element of the control vector,
$\alpha_{c}$. With this decomposition, the next theorem establishes that CVI
applied to separable systems will converge to the true optimal value.

###### Theorem 5

Optimality of CVI on Separable Systems. Consider the CVI Algorithm for a
separable TI-MDP. The CVI algorithm will converge to the true optimal value,
$\widehat{V}=V^{*}$.

#### Proof:

First it will be shown that CVI updates on separable systems converge to a
unique fixed point, and then that this unique fixed point is the true optimal
value.

As shown in the proof of Lemma 5, the VI update for a separable system can be
written as

$\displaystyle V^{*}(s)=\sum_{c}V^{c,*}(s).$ (19)

Recall that $\mathbf{T}_{\pi}V^{c}(s)$ is the evaluation of the Bellman
operator at $\alpha$ without the maximization step. Consider CVI-type updates
of the form,

$\displaystyle\widehat{V}^{c,*}(s)$
$\displaystyle=\mathbf{T}_{\pi}\dots\mathbf{T}_{\pi}\mathbf{T}^{c}\mathbf{T}_{\pi}\dots\mathbf{T}_{\pi}V_{0}^{c}(s).$
(20)

Define the operator
$\overline{\mathbf{T}}^{c}=\mathbf{T}_{\pi}\dots\mathbf{T}_{\pi}\mathbf{T}^{c}V^{c}(s)$
where $\mathbf{T}^{c}$ preforms the maximization step and produces candidate
$\alpha$ that is then evaluated $C-1$ times on the resulting value. Note that
$\overline{\mathbf{T}}^{c}$ is a contraction (with parameter $\gamma^{C}$), so
repeated applications of $\overline{\mathbf{T}}^{c}$ will converge to a unique
fixed point. Any additional evaluations of $\mathbf{T}_{\pi}$ after
convergence of $\overline{\mathbf{T}}^{c}$ will leave the final value
unchanged, and any applications of $\mathbf{T}_{\pi}$ to $V_{0}$ (with
arbitrary $\pi$) before $\overline{\mathbf{T}}^{c}$ will change the initial
guess to $V_{0}^{\prime}$, but will not change the location of the convergence
point.

The next step is to show that the convergence point of CVI is equal to the
true optimal value. Apply $\overline{\mathbf{T}}^{c}$ to the true optimal
components $V^{c,*}(s)$ to find,

$\displaystyle\overline{\mathbf{T}}^{c}V^{c,*}$
$\displaystyle=\mathbf{T}_{\pi}\dots\mathbf{T}_{\pi}\mathbf{T}^{c}V^{c,*},$
(21) $\displaystyle=\mathbf{T}_{\pi}\dots\mathbf{T}_{\pi}V^{c,*}=V^{c,*}.$
(22)

$V^{c,*}$ is a fixed point of $\overline{\mathbf{T}}^{c}$, and therefore the
fixed points of $\overline{\mathbf{T}}^{c}$ and $\mathbf{T}^{c}$ are equal for
all $c$. $\square$

This key result shows that an optimal policy of any separable TI-MDP may be
found via CVI. The structure of the CVI algorithm implies a natural
distributed extension whereby the policy for each cluster may be optimized in
parallel. For separable systems, consider the following distributed learning
algorithm shown in Algorithm 2. Consider a setup of $C$ machines; let each
machine optimize the actions for one cluster, and then transmit the final
actions to construct the final policy. Note that the optimization step over
each cluster is standard VI over the actions for each $\alpha_{c}$.

$V_{0}(s)\leftarrow 0,\ \forall s\in\mathcal{S}$;

for  _Each Cluster $c\in\\{1,\dots,C\\}$_ do

$k=-1$;

while  _$\|V_{k}-V_{k-1}\|_{\infty} >\epsilon$_ do

$k=k+1$;

$V_{k+1}^{c}(s)\leftarrow\mathbf{T}^{c}V^{c}(s),\ \forall s\in\mathcal{S}$;

end while

$\alpha_{c}(s)\leftarrow\operatorname*{arg\,max}_{\alpha}\mathbf{T}^{c}V_{k}^{c}(s),\
\forall s\in\mathcal{S}$;

Return $V^{c}(s),\alpha_{c}(s)$;

end for

$V=\sum_{c\in\mathcal{C}}V^{c}$;

Algorithm 2 Clustered Value Iteration - Separable (CVI-S)

As expected, CVI-S on separable systems will recover the true optimal value
and an optimal policy. Notice that no communication between nodes is needed
but for reporting the local fixed point. The additive structure of the rewards
and the conditional independence of the agents’ decision-making processes
enables this setup.

###### Theorem 6

Consider the CVI-S Algorithm 2 for a separable TI-MDP. The CVI-S algorithm
will converge to the true optimal value and an optimal policy.

#### Proof:

By Lemma 5, $V_{k}(s)=\sum_{c}V_{k}^{c}(s)$ for every $k$ and will converge as
$k\to\infty$. Take the limit of $k$ to find,

$\displaystyle
V^{*}(s)=\lim_{k\to\infty}V_{k}(s)=\sum_{c\in\mathcal{C}}\lim_{k\to\infty}V_{k}^{c}(s).$

Each $\lim_{k\to\infty}V_{k}^{c}(s)$ will converge to a unique fixed point and
can be summed to find $V^{*}(s)$. $\square$

To recap, the controller aims to attain a better value by using a clustered
control policy. It has been discussed that standard methods to solve for such
a control policy depend on searching the action space, the size of which has
exponential dependence on the number of clusters. The proposed CVI algorithm
makes use of the clustered Bellman operator, which optimizes over one
dimension of the control policy at any iteration. In general repeated use of
the clustered Bellman operator will not yield an optimal policy, but its
computation time has no dependence on the number of clusters. Finally, Theorem
(5) states that when applied to separable systems, CVI solves for a true
optimal policy. Therefore, the user may keep all the complexity savings and
value improvement, and be assured in the policy’s optimality.

##  5 Choosing Cluster Assignments

Leading up to this section, it has been assumed that the cluster assignments
are known _a priori_. This is a reasonable assumption for applications where
classes of agents are apparent or existing; i.e. category of customer or type
of robot. As seen in the definition of separability, classes of agents may be
defined in terms of similarity of reward function. For general multi-agent
MDPs, however, the clustered approach may be used simply to increase the
received value without relying on intuition about agent classes. This is the
setting now of focus, where a planner desires the best $C$ clusters in terms
of value.

###### Definition 6

An _optimal $C$ clustering assignment_ for a TI-MDP is $\mathcal{C^{*}}$ such
that the resulting optimal value is maximal;

$\displaystyle\max_{\mathcal{C}}\ V^{*}(s)$ (23) $\displaystyle\text{s.t. }\
|\mathcal{C}|=C.$

Note that (23) is a discrete optimization problem that requires $O(C^{N})$
evaluations if solved by enumeration. In general, this problem is known to be
NP-hard [33].

In this section, an approximate solution to the optimization problem (23) will
be explored. All discussion will be for separable TI-MDPs, both because CVI is
optimal for this class of problems, and to use the structure of the reward
function.

###  5.1 Submodularity of Value Functions

Let $V(\mathcal{C}_{k})$ be a shorthand to mean the value function associated
with clustering assignment $\mathcal{C}$ that consists of $k$ clusters. Let
$\mathcal{C}^{*}_{k}$ be the optimal clustering assignment of $k$ clusters,
and let $\widehat{\mathcal{C}}_{k}$ be the clustering assignment of $k$
clusters as found by an approximate algorithm.

The first useful definition is for submodular functions, which is a notion
often used in discrete optimization.

###### Definition 7

Given a finite set $E$, a _submodular_ function $f:2^{E}\to\mathbb{R}$ is such
that for every $A\subseteq B\subseteq E$ and $i\in E\setminus B$,

$f(A\cup\\{i\\})-f(A)\geq f(B\cup\\{i\\})-f(B).$ (24)

Furthermore, $f$ is _monotone_ if $f(B)\geq f(A)$.

Submodularily is a useful property for set optimization as it means the
benefit of adding more elements to a set decreases as the set grows in size;
i.e. diminishing returns. Maximizing a submodular function subject to a
dimensionality constraint, for example, means that the possible improvement
between the $k$ and $k+1$ indices is upper bounded.

It can be shown that the value function for separable TI-MDPs is a submodular
function with respect to the number of agents. With the following result, the
optimization problem (23) may be approached with techniques developed for
submodular function.

###### Lemma 6

Submodularity of TI-MDP. For agent-separable $r(s,\bm{\alpha})$, $V(s)$ is
submodular with respect to the number of agents. More specifically, for sets
of agents $A\subseteq B\subseteq\mathcal{N}$ and agent
$n\in\mathcal{N}\setminus B$,

$V^{A\cup\\{n\\}}(s)-V^{A}(s)\geq V^{B\cup\\{n\\}}(s)-V^{B}(s),$ (25)

where $V^{N}(s)$ is the value function with respect to the set of agents $N$.

#### Proof:

By VI, $V(s)=\lim_{k\to\infty}\mathbf{T}V_{k}(s)$, so it suffices to show that
(25) holds for any $k$th application of the Bellman operator.

$\displaystyle V_{1}^{A}(s)=r(s_{A});\
V_{1}^{A\cup\\{n\\}}=r(s_{A\cup\\{n\\}});$ $\displaystyle
V_{1}^{B}(s)=r(s_{B});\ V_{1}^{B\cup\\{n\\}}=r(s_{B\cup\\{n\\}}).$

The reward function for an agent-separable TI-MDP can be written in the form
$r(s,\bm{\alpha})=\sum_{n}r_{n}(s_{n},\bm{\alpha}_{n})$. Linear functions are
modular (submodular), so $r(s,\bm{\alpha})$ is submodular and therefore
$V_{1}(s)$ is submodular.

Now show for general $k$.

$\displaystyle\mathbf{T}V_{k}^{B\cup\\{n\\}}(s)-\mathbf{T}V_{k}^{B}(s)$
$\displaystyle\begin{split}=\sum_{s_{B\cup\\{n\\}}^{\prime}}p(s_{B\cup\\{n\\}}^{\prime}|s,\bm{\alpha})[r(s_{B\cup\\{n\\}},\bm{\alpha})+\gamma
V^{B\cup\\{n\\}}_{k-1}(s^{\prime})]\\\
-\sum_{s_{B}^{\prime}}p(s_{B}^{\prime}|s,\bm{\alpha})[r(s_{B},\bm{\alpha})+\gamma
V^{B}_{k-1}(s^{\prime})]\end{split}$
$\displaystyle\begin{split}=\sum_{s_{B}^{\prime}}p(s_{B}^{\prime}|s,\bm{\alpha})\Big{[}\sum_{s_{\\{n\\}}^{\prime}}p(s_{\\{n\\}}^{\prime}|s,\bm{\alpha})[r(s_{B\cup\\{n\\}},\bm{\alpha})+\gamma
V^{B\cup\\{n\\}}_{k-1}(s^{\prime})]\\\ -[r(s_{B},\bm{\alpha})+\gamma
V^{B}_{k-1}(s^{\prime})]\Big{]}\end{split}$
$\displaystyle\begin{split}=\sum_{s_{B}^{\prime}}p(s_{B}^{\prime}|s,\bm{\alpha})\Big{[}\sum_{s_{\\{n\\}}^{\prime}}p(s_{\\{n\\}}^{\prime}|s,\bm{\alpha})\Big{[}r(s_{B\cup\\{n\\}},\bm{\alpha})-r(s_{B},\bm{\alpha})\\\
+\gamma\Big{(}V^{B\cup\\{n\\}}_{k-1}(s^{\prime})-V^{B}_{k-1}(s^{\prime})\Big{)}\Big{]}\Big{]}\end{split}$
$\displaystyle\begin{split}\leq\sum_{s_{B}^{\prime}}p(s_{B}^{\prime}|s,\bm{\alpha})\Big{[}\sum_{s_{\\{n\\}}^{\prime}}p(s_{\\{n\\}}^{\prime}|s,\alpha)\Big{[}r(s_{A\cup\\{n\\}},\bm{\alpha})-r(s_{A},\bm{\alpha})\\\
+\gamma\Big{(}V^{A\cup\\{n\\}}_{k-1}(s^{\prime})-V^{A}_{k-1}(s^{\prime})\Big{)}\Big{]}\Big{]}\end{split}$
$\displaystyle\begin{split}=\sum_{s_{A}^{\prime}}p(s_{A}^{\prime}|s,\bm{\alpha})\sum_{s_{B\setminus
A}^{\prime}}p(s_{B\setminus
A}^{\prime}|s,\bm{\alpha})\Big{[}\sum_{s_{\\{n\\}}^{\prime}}p(s_{\\{n\\}}^{\prime}|s,\bm{\alpha})\\\
\Big{[}r(s_{A\cup\\{n\\}},\bm{\alpha})-r(s_{A},\bm{\alpha})+\gamma\Big{(}V^{A\cup
i}_{k-1}(s^{\prime})-V^{A}_{k-1}(s^{\prime})\Big{)}\Big{]}\Big{]}\end{split}$
$\displaystyle\begin{split}=\sum_{s_{A}^{\prime}}p(s_{A}^{\prime}|s,\bm{\alpha})\Big{[}\sum_{s_{\\{n\\}}^{\prime}}p(s_{\\{n\\}}^{\prime}|s,\bm{\alpha})\Big{[}r(s_{A\cup\\{n\\}},\bm{\alpha})-r(s_{A},\bm{\alpha})\\\
+\gamma\Big{(}V^{A\cup\\{n\\}}_{k-1}(s^{\prime})-V^{A}_{k-1}(s^{\prime})\Big{)}\Big{]}\Big{]}\end{split}$
$\displaystyle=\mathbf{T}V_{k}^{A\cup\\{n\\}}(s)-\mathbf{T}V_{k}^{A}(s)$

$\square$

###### Lemma 7

Monotonicity of TI-MDPs: For monotone $r(s,\bm{\alpha})$, $V(s)$ is monotone
with respect to the number of agents.

#### Proof:

This again can be shown via induction.

$\displaystyle
V_{1}^{B}(s)-V_{1}^{A}(s)=r(s_{B},\bm{\alpha})-r(s_{A},\bm{\alpha})\geq 0$

Induction on $k$:

$\displaystyle\mathbf{T}V_{k}^{B}(s)-\mathbf{T}V_{k}^{A}(s)$
$\displaystyle\begin{split}=\sum_{s^{\prime}_{A}}p(s^{\prime}_{B}|s,\bm{\alpha})\Big{[}\sum_{s^{\prime}_{B\setminus
A}}p(s^{\prime}_{B\setminus
A}|s,\bm{\alpha})\Big{[}r(s_{B},\bm{\alpha})+\gamma
V_{k-1}^{B}(s^{\prime})\Big{]}\\\ -r(s_{A},\bm{\alpha})+\gamma
V_{k-1}^{A}(s^{\prime})\Big{]}\end{split}$
$\displaystyle\begin{split}=\sum_{s^{\prime}_{A}}p(s^{\prime}_{B}|s,\bm{\alpha})\sum_{s^{\prime}_{B\setminus
A}}p(s^{\prime}_{B\setminus
A}|s,\bm{\alpha})\Big{[}r(s_{B},\bm{\alpha})-r(s_{A},\bm{\alpha})\\\
+\gamma(V_{k-1}^{B}(s^{\prime})-V_{k-1}^{A}(s^{\prime}))\Big{]}\geq
0\end{split}$

By induction, $\mathbf{T}V_{k}^{B}\geq\mathbf{T}V_{k}^{A}$ for all $k$, so
therefore $\lim_{k\to\infty}V_{k}^{B}(s)\geq\lim_{k\to\infty}V_{k}^{A}(s)$ and
$V^{B}(s)\geq V^{A}(s)$.

$\square$

The results in this section establish that properties of submodularity may be
used to analyze separable TI-MDPs. This structure will help find methods of
solving the clustering assignment problem (23) with theoretical guarantees.

###  5.2 Greedy Clustering

With the notions of submodularity established, we return to the optimal
clustering problem. The optimization problem can be restated as,

$\displaystyle\max_{\mathcal{C}}\sum_{c=1}^{C}V^{*,c}(s),$ (26)
$\displaystyle\text{s.t.}\ c_{1}\cup\dots\cup c_{C}=\mathcal{N},$
$\displaystyle c_{i}\cap c_{j}=\emptyset,\forall i,j\in[1,C],i\neq j.$

As discussed in the introduction, (26) can equivalently be represented as an
optimization problem subject to a partition matroid constraint, for which
there exists a $(1-1/e)$ approximate algorithm [33]. The presented method
creates a continuous approximation of the discrete objective function via
random sampling, and then rounds the solution of the continuous problem to a
feasible point in the matroid. While this method provides a close
approximation to the optimal, it was not formulated specifically for MDP value
functions and requires a complicated implementation for the approximation
subroutines. In this section we will explore a more simple construction that
builds upon the optimality of CVI queries on separable systems.

In [31], Zhao et. al. suggest a Greedy Splitting Algorithm (GSA) to solve (26)
for the minimization case that achieves an approximation
$f(\widehat{\mathcal{C}})\leq(2-\frac{2}{k})f(\mathcal{C}^{*})$ for monotonone
submodular $f$ in $O(kN^{3}\theta)$ time where $\theta$ is the time to query
$f$. This approach begins with all the agents as one cluster, and then takes
for some desired number of clusters $k$, the best possible refinement of the
clusters determined for $k-1$. Note that this method only requires computation
of $V$ for some clustering configuration, which is a perfect use case for CVI.
However, adapting GSA to a maximization problem loses the error bound
guarantees due to non-negativity constraints. In general, the maximization of
submodular functions subject to a cardinality constraint is a much harder
problem than minimization [33], and includes famous problems such as the
maximum coverage problem.

Nevertheless, in this paper we suggest adapting GSA for value maximization of
cluster assignments because it guarantees value improvement with each split,
and because it only requires calls to a CVI subprocess. Recall the original
motivations for cluster-based control: (1) _a priori_ constraints or agent
types, and (2) to achieve better value from more sophisticated controls. This
section focuses on the second motivation; a simple method like greedy
splitting is easy to implement, only needing the existing resources to
calculate $V$, and gives monotonically increasing values for increasing $k$. A
maximization version of GSA is presented in Algorithm 3 and it will be shown
that the algorithm finds clustering assignments whose values form a submodular
lower bound of the optimal values of (26).

In general, the term $C$ will be used to refer to the desired final number of
clusters, and $k$ will refer to the number clusters at an intermediate step.
The initialization defines one cluster of all the agents. At each subsequent
query for new clusters, the algorithm searches for some existing cluster $U$
and a split $\\{U\setminus X,X\\}$ that provides the most value improvement.
This is repeated until $C$ clusters are achieved and the final value is
returned. The number of possible sets formed by splitting $n$ elements split
into $k$ disjoint subsets may found by the Stirling number of the second kind
$S(n,k)$. Therefore the number of possible splits across some clustering
assignment is $\sum_{c\in\mathcal{C}}S(|c|,2)$.

$\widehat{\mathcal{C}}_{1}=\\{\mathcal{N}\\}$;

$\widehat{V}_{1}=\text{CVI}(\widehat{\mathcal{C}}_{1})$;

for  _$k\in\\{2,\dots,C\\}$_ do

$(X_{k},U_{k-1})\leftarrow\text{argmax}\\{V(X)+V(U\setminus X)-V(U)\ |\
\emptyset\subset X\subset U,\ U\in\widehat{\mathcal{C}}_{k-1}\\}$;

$\widehat{\mathcal{C}}_{k}\leftarrow\\{\widehat{\mathcal{C}}_{k-1}\setminus
U_{k-1}\\}\cup\\{X_{k},U_{k-1}\setminus X_{k}\\}$;

$\widehat{V}_{k}=\text{CVI}(\widehat{\mathcal{C}}_{k})$;

end for

Algorithm 3 Greedy Splitting Algorithm - Reward

###### Remark 1

The optimal values for an optimal $k$-clustering is lower bounded by the
optimal value for a clustering found by GSA-R.

$\displaystyle V^{*}(\mathcal{C}^{*}_{k})\geq
V^{*}(\widehat{\mathcal{C}}_{k})$

The clustering assignments found by GSA-R are optimal for $k=1,2,N$, i.e.
$\widehat{\mathcal{C}}_{1}=\mathcal{C}^{*}_{1},\widehat{\mathcal{C}}_{2}=\mathcal{C}^{*}_{2},\widehat{\mathcal{C}}_{N}=\mathcal{C}^{*}_{N}$.
For the case $k=2$, this can be seen due to the fact that optimizing over the
set of 2-cluster assignments is equivalent to optimizing over one split.

###### Lemma 8

Monotonicity of Splitting. Consider a TI-MDP with a clustering assignment with
$k$ clusters. The optimal value $V^{*}(\mathcal{C}_{k+1})$ will at least be
equal to $V^{*}(\mathcal{C}_{k})$ if the $k+1$ cluster is formed by splitting
one of the existing $k$ clusters.

#### Proof:

Proof by induction.

Base case: Assume there are $k=2$ clusters, $c_{1}$ and $c_{2}$. The value of
a state under $\pi^{*}$ is,

$V^{*}_{k=2}(s)=\max_{\alpha_{1},\alpha_{2}}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\alpha_{c_{1}},\alpha_{c_{2}}\\})(r(s,\\{\alpha_{c_{1}},\alpha_{c_{2}}\\})+\gamma
V^{*}(s^{\prime})).$

If $a_{c_{1}}=a_{c_{2}}$, then this is equivalent to the one-cluster case and
we recover the same value $V^{*}_{k=2}(s)=V^{*}_{k=1}(s)$.

Else if $a_{c_{1}}\neq a_{c_{2}}$ then,

$\displaystyle
V^{*}_{k=2}(s)=\max_{\alpha_{c_{1}},\alpha_{c_{2}}}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\alpha_{c_{1}},\alpha_{c_{2}}\\})(r(s,\\{\alpha_{c_{1}},\alpha_{c_{2}}\\})+\gamma
V^{*}(s^{\prime})),$
$\displaystyle\geq\max_{\alpha}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\alpha,\alpha\\})(r(s,\\{\alpha,\alpha\\})+\gamma
V^{*}(s^{\prime}))=V^{*}_{k=1}(s).$

Inductive step: Say there are $k^{\prime}$ clusters and that the controller
uses policy $\Pi^{*}$. Take cluster $c^{\prime}$ and split it into two
clusters, $\\{c_{1}^{\prime},c_{2}^{\prime}\\}$ where $c_{1}^{\prime}\cup
c_{2}^{\prime}=\emptyset$ and $c_{1}^{\prime}\cap c_{2}^{\prime}=c^{\prime}$.
This forms $k^{\prime}+1$ clusters. Again if
$\alpha_{c_{1}^{\prime}}=\alpha_{c^{\prime}}$ and
$\alpha_{c_{2}^{\prime}}=\alpha_{c^{\prime}}$, then we recover the same value
$V^{*}_{k^{\prime}}(s)=V^{*}_{k^{\prime}+1}(s)$. However if
$\alpha_{c_{1}^{\prime}}\neq\alpha_{c^{\prime}}$ or
$\alpha_{c_{2}^{\prime}}\neq\alpha_{c^{\prime}}$, then,

$\displaystyle V^{*}_{k^{\prime}+1}(s)$
$\displaystyle\begin{split}=\max_{\alpha_{1},\dots,\alpha_{c_{1}^{\prime}},\alpha_{c_{2}^{\prime}}}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\alpha_{1},\dots,\alpha_{c_{1}^{\prime}},\alpha_{c_{2}^{\prime}}\\})\\\
\times(r(s,\\{\alpha_{1},\dots,\alpha_{c_{1}^{\prime}},\alpha_{c_{2}^{\prime}}\\})+\gamma
V^{*}(s^{\prime})),\end{split}$
$\displaystyle\begin{split}\geq\max_{\alpha_{1},\dots,\alpha_{k^{\prime}},\alpha_{k^{\prime}}}\sum_{s^{\prime}}p(s^{\prime}|s,\\{\alpha_{1},\dots,\alpha_{k^{\prime}},\alpha_{k^{\prime}}\\})\\\
\times(r(s,\\{\alpha_{1},\dots,\alpha_{k^{\prime}},\alpha_{k^{\prime}}\\})+\gamma
V^{*}(s^{\prime})),\end{split}$ $\displaystyle=V^{*}_{C^{\prime}}(s).$

$\square$

This result on the splittings further shows that the resulting values for the
optimal clustering problem (26) monotonically improve for increasing $k$.

###### Lemma 9

_Monotonicity of Optimal Clusterings._ Consider a separable TI-MDP. The series
of optimal values for each optimal clustering assignment is a monotonically
increasing sequence:

$\displaystyle V^{*}(\mathcal{C}^{*}_{1})\leq\dots\leq
V^{*}(\mathcal{C}^{*}_{k})\leq\dots\leq V^{*}(\mathcal{C}^{*}_{C}).$ (27)

#### Proof:

By Lemma 8, $V^{*}(\mathcal{C}_{k}^{*})\leq V^{*}(\mathcal{C}_{k+1})$ where
$\mathcal{C}_{k+1}$ is a split of $\mathcal{C}_{k}^{*}$. Then
$V^{*}(\mathcal{C}_{k+1})\leq V^{*}(\mathcal{C}_{k+1}^{*})$ and the result
holds. $\square$

Note that Lemma 8 holds for non-separable TI-MDPs. For the separable case, we
can find better performance guarantees in that the values have diminishing
returns for increased numbers of clusters.

###### Theorem 7

The sequence of $\widehat{\mathcal{C}}_{k}$ found by GSA-R produces submodular
optimal values for monotone, separable $r(s,\bm{\alpha})$.

$\displaystyle
V^{*}(\widehat{\mathcal{C}}_{k+1})-V^{*}(\widehat{\mathcal{C}}_{k})\leq
V^{*}(\widehat{\mathcal{C}}_{k})-V^{*}(\widehat{\mathcal{C}}_{k-1})$

#### Proof:

In this proof, all value functions are assumed to be evaluated for the optimal
policy, but the superscript notation is omitted.

_Base Case:_ Need to show:
$V(\widehat{\mathcal{C}}_{2})-V(\widehat{\mathcal{C}}_{1})\leq
V(\widehat{\mathcal{C}}_{1})-V(\widehat{\mathcal{C}}_{0})$, but for zero
clusters $V(\widehat{\mathcal{C}}_{0})=0$, so need to show
$V(\widehat{\mathcal{C}}_{2})-V(\widehat{\mathcal{C}}_{1})\leq
V(\widehat{\mathcal{C}}_{1})$. Denote the set
$\widehat{\mathcal{C}}_{2}=\\{U,W\\}$. By Lemma 7,
$V(\widehat{\mathcal{C}}_{1})\geq V(U)$ and $V(\widehat{\mathcal{C}}_{1})\geq
V(W)$. Thus $V(\widehat{\mathcal{C}}_{2})=V(U)+V(W)\leq
2V(\widehat{\mathcal{C}}_{1})$ as desired.

_Induction:_ The goal is to show that
$V(\widehat{\mathcal{C}}_{k+1})-V(\widehat{\mathcal{C}}_{k})\leq
V(\widehat{\mathcal{C}}_{k})-V(\widehat{\mathcal{C}}_{k-1})$.

Let $U_{k}\in\widehat{\mathcal{C}}_{k}$ be the cluster that is split into
$X_{k+1}$ and $Y_{k+1}$ to form $\widehat{\mathcal{C}}_{k+1}$, i.e.
$X_{k+1}\cup Y_{k+1}=U_{k}$, $X_{k+1}\cap Y_{k+1}=\emptyset$. There are two
cases: either $U_{k}\subset U_{k-1}$ or $U_{k}\not\subset U_{k-1}$.

$\displaystyle
V(\widehat{\mathcal{C}}_{k+1})-V(\widehat{\mathcal{C}}_{k})=V(X_{k+1})+V(Y_{k+1})-V(U_{k})$

If $U_{k}\not\subset U_{k-1}$ then optimally splitting $U_{k-1}$ provided a
bigger value increase than optimally splitting $U_{k}$. This is because both
sets were available to select to split at stage $k-1$, but the greedy
algorithm selected $U_{k-1}$. Thus $V(X_{k})+V(Y_{k})-V(U_{k-1})\geq
V(X_{k+1})+V(Y_{k+1})-V(U_{k})$ and therefore
$V(\widehat{\mathcal{C}}_{k})-V(\widehat{\mathcal{C}}_{k-1})\geq
V(\widehat{\mathcal{C}}_{k+1})-V(\widehat{\mathcal{C}}_{k})$.

In the other case, $U_{k-1}$ is split, and then $X_{k}$ or $Y_{k}$ are
selected as the next $U_{k}$. Say that $X_{k}=U_{k-1}$. Need to show:

$\displaystyle V(X_{k+1})+V(Y_{k+1})-V(X_{k+1}\cup Y_{k+1})$
$\displaystyle\leq V(X_{k})+V(Y_{k})-V(X_{k}\cup Y_{k})$
$\displaystyle=V(X_{k+1}\cup Y_{k+1})+V(Y_{k})-V(X_{k+1}\cup Y_{k+1}\cup
Y_{k})$ (28)

By submodularity,

$\displaystyle V(X_{k+1}\cup Y_{k+1})-V(X_{k+1})-V(Y_{k+1})$
$\displaystyle\geq V(X_{k+1}\cup Y_{k+1}\cup Y_{k})-V(X_{k+1}\cup
Y_{k})-V(Y_{k+1})$

Therefore to claim (28), need,

$\displaystyle V(X_{k+1}\cup Y_{k+1})+V(Y_{k})$ $\displaystyle\geq
V(X_{k+1}\cup Y_{k})+V(Y_{k+1})$

Recall that $X_{k+1}\cup Y_{k+1}\cup Y_{k}=U_{k-1}$. The above equation shows
the value of two possible splittings of $U_{k-1}$: the LHS is the split
$\\{X_{k+1}\cup Y_{k+1},Y_{k}\\}$ and the RHS is the split $\\{X_{k+1}\cup
Y_{k},Y_{k+1}\\}$. As the algorithm selects the best splits in a greedy
fashion, the LHS is a better split and thus has a greater value. Thus (28)
holds, and so does the original claim. $\square$

Theorem 7 shows that GSA-R finds clustering assignments whose optimal values
are a submodular lower bound of the optimal clusters’ values. In addition,
this bound is tight at the endpoints.

##  6 Examples

In this section the CVI and GSA-R algorithms are explored in simulation. In
the first example, the results and computation times of VI versus CVI are
studied, as well as how CVI performs within our established error bound. The
second example looks at the GSA-R technique, and demonstrates its computation
savings versus a naive approach. Finally, an applied example where agents
assign themselves to channels subject to bandwidth and costs constraints is
presented.

###  6.1 VI vs CVI Examples

Figures 1 and 2 give the results of the CVI algorithm as compared to VI on
non-separable and separable systems, respectively. In both cases, a system of
$N=7$ agents was considered, where each agent selected between binary choices
at each time step. With the MDP states defined as the joint strategies of the
system, the overall state space had a size of $2^{7}=128$. The controller was
given $M=3$ actions that may be assigned to any particular cluster, leading to
an action space of size $3^{C}$ where $C$ is the number of clusters.
Appropriate transition matrices were randomly generated, as well as
deterministic non-separable and separable state reward functions of the form
$r(s,\bm{\alpha})\triangleq r(s)$.

The graphs show the value $\|V^{*}\|$ averaged over every possible clustering
assignment for a fixed $C$ and normalized by the maximum possible value when
$C=7$. The basic case, where $C=1$, is plotted across each $C$ to show the
increase in value attained by using cluster-based control. The black dot on
each bar shows the $\|\widehat{V}\|$ achieved via CVI, again averaged across
all clustering assignments and normalized by the maximum optimal value. The
CVI value is shown with the minimum and maximum error bounds as found by (12)
and (13).

Figure 1: Performance of cluster-based control policies on a non-separable
system for different $C$.

Figure 2: Performance of cluster-based control policies on a separable system
for different $C$.

These results exemplify the performance of CVI as compared to VI. Clearly
Figure 2 shows that CVI recovers the same values as VI for separable systems.
In the general case, Figure 1 shows that $\|\widehat{V}\|$ is consistently in
the best side of its error range, being close to the true $\|V^{*}\|$.

Finally, the red squares show the ratio of the computation time under VI and
CVI. The simulations were written in MATLAB, with the only difference in
implementation being that VI optimized over the whole action space at each
iteration, whereas CVI optimized over a specified subset of actions. These
results confirm that the computation time of VI scales exponentially with the
number of clusters, which is an increase not seen with CVI. For example,
consider the non-separable case where $C=7$. CVI converged about 234 times
faster than VI. While the computational savings is primarily reflected in the
per-iteration time, it is reasonable to consider than higher $C$ means that
more total iterations are needed. In fact, CVI for $C=7$ was only about 3x
slower than CVI for $C=1$, whereas VI for $C=7$ was about 750x slower than VI
for $C=1$.

###  6.2 Greedy Clustering

This next example explores the utility of selecting clustering assignments
with the GSA-R algorithm. Figure 3 shows the results from a randomly generated
separable TI-MDP constructed with $N=10$ agents for a state space of size
$2^{10}=1024$. The bars show $\|V^{*}\|$ (again normalized by the maximum
where $C=10$) produced by clustering assignments selected by the greedy
splitting technique. Note that the values display the diminishing returns
property as more clusters are considered, thus demonstrating the results of
Theorem 7.

The black dots here demonstrate the ratio of the number of clustering
assignments checked by a naive brute-force method versus using the greedy
splitting technique. In the naive method, every possible assignment of $N$
agents split into $C$ clusters is evaluated, which leads to $S(N,C)$ possible
combinations. For GSA-R, only refinements of the previous clustering
assignment are considered; for $C=3,\dots,8$ this leads to a reduction in the
number of evaluations. For the $C=9,10$ cases, however, solving directly via
the naive method is more efficient as $S(N,C)$ is small and GSA-R requires
iterating from $k=1,2,\dots,C$. The resulting curve corroborates intuition
that the greatest number of possible clustering assignments is achieved at
$C=N/2$, where in this case GSA-R evaluated about 70x fewer cases yet achieved
more than $99\%$ of the maximum value. The results of this simulation imply
that for applications where using $C=N$ is not feasible either computationally
or in deployment, GSA-R is an effective technique for finding a clustering
assignment that achieves a good optimal value.

Figure 3: Performance of greedy splitting to find clustering assignments.

###  6.3 Channel Assignment Example

In this section we consider a scenario where agents attempt to assign
themselves to different channels subject to bandwidth constraints and costs.
This scenario will exemplify how a MAS, described as a game, can be abstracted
to a MDP framework and controlled with CVI and GSA-R techniques.

Let there be three channels of low, medium, and high bandwidths (20, 50, 100).
Each agent in the set of $N=6$ agents selects a channel to use at each time
step. The agents evaluate each channel with a utility function of the form,

$\displaystyle u_{n}(x)=\frac{b(x)}{1+\sum_{n^{\prime}\neq
n}\mathbbm{1}(s_{n^{\prime},t}=x)}-\beta_{n}\nu(x)$

where $b(x)$ is the bandwidth of channel $x$, $\nu(x)$ is the cost of using
the channel, and $\beta_{n}$ is a scaling factor for each $n$ chosen randomly
from $[0,1]$. This utility function can be interpreted as the effective
bandwidth for $n$ had they chosen $x$ minus a scaled cost to use the channel.
All agents are assumed to use a best-response style decision process, leading
to a large sparse transition matrix describing 729 states. The cost structure,
as chosen by the controller, can be one of the following structures:

$\nu(x,\alpha)$ | Low BW | Med BW | High BW
---|---|---|---
$\alpha_{1}$ | 0 | 10 | 30
$\alpha_{2}$ | 1 | 15 | 50
$\alpha_{3}$ | 10 | 50 | 100

Consider two scenarios for the controller.

#### Scenario 1: Maximum Revenue

Here the controller aims to maximize their received payments from the agents.
The overall reward to the controller is thus
$r(s,\bm{\alpha})=\sum_{n\in\mathcal{N}}\nu(s_{n},\bm{\alpha}_{n})$ which is
clearly agent-separable. Note that this reward function depends on both

#### Scenario 2: Desired Configuration

This scenario represents the case where the controller wants a specific action
configuration. In this example, the controller wants all the agents to choose
the medium bandwidth channel. Their reward function is thus
$r(s,\bm{\alpha})=\sum_{n\in\mathcal{N}}\mathbbm{1}(s_{n}=\text{medium})$,
which again is agent-separable.

These scenarios were solved and the results are shown in Figure 4. Note that
each row is normalized by the maximum value achieved when $C=6$. First, we
immediately notice that introducing clusters improves the performance. As the
reward structure is separable, we can use CVI to solve for optimal control
policies given a clustering assignment chosen by GSA-R. Second, these examples
demonstrate scenarios in which agent-separable reward functions enable
desirable outcomes. Finally, note that GSA-R implies a natural stopping
criterion. In practice the controller can observe the negligible value
improvement from two to three clusters (in either case), and then from the
diminishing returns property conclude that the policy for three clusters
achieved near-optimal performance.

$\frac{\|V^{*}\|}{\|V^{*}_{C=6}\|}$ | C=1 | C=2 | C=3 | C=4 | C=5 | C=6
---|---|---|---|---|---|---
Scenario 1 | 0.8409 | 0.9757 | 0.9953 | 0.9993 | 0.9996 | 1.0000
Scenario 2 | 0.8825 | 0.9848 | 0.9936 | 0.9997 | 0.9999 | 1.0000
Figure 4: Results of the channel assignment example using CVI and GSA-R on two
different separable reward functions.

##  7 Conclusion

In this work we examined cluster-based control techniques on a multi-agent
system to achieve behavioral objectives. A collective of agents, whose
behavior may be learned or abstracted from a known model, can be represented
as a transition-independent Markov decision process under mild assumptions.
While the classic setup has the controller assign an action to the system,
better performance may be achieved by partitioning agents into groups and
giving each group its own action. This cluster-based approach can greatly
increase the attained value, however solving through standard techniques such
as value iteration and policy iteration become prohibitively slow due to huge
action space. This work details a solution in clustered value iteration, which
takes a “round-robin” approach to policy optimization. This algorithm’s
convergence properties are studied, and it is shown that the true optimal may
be attained in systems whose reward functions have a separable quality.

The second half of this work examined techniques for optimally clustering
agents. An iterative greedy splitting technique is proposed as a desirable
approach, as it provides monotonic, submodular improvement in value, and
requires significantly less computation than a naive approach. Examples of
both clustered value iteration and the greedy splitting clustering are
explored in simulation under a variety of scenarios.

While inspired by multi-agent systems, this formulation has relevance to other
reinforcement learning problems, specifically in the case of complicated
action spaces. These techniques may be layered with approaches like value
function approximation for the combined benefits for handling large state and
action spaces. Future work can study scalability of both spaces subject to
large systems of agents, as well as more sophisticated techniques to choose
cluster configurations.

## Acknowledgment

This material is based upon work supported by the National Science Foundation
Graduate Research Fellowship Program under Grant No. DGE1745016. Any opinions,
findings, and conclusions or recommendations expressed in this material are
those of the author(s) and do not necessarily reflect the views of the
National Science Foundation. In addition, the authors would like to
acknowledge support from the Hsu Chang Memorial Fellowship in ECE.

## References

  * [1] P. Stone and M. Veloso, “Multiagent systems: A survey from a machine learning perspective,” _Autonomous Robots_ , vol. 8, no. 3, pp. 345–383, 2000.
  * [2] A. Dorri, S. S. Kanhere, and R. Jurdak, “Multi-agent systems: A survey,” _Ieee Access_ , vol. 6, pp. 28 573–28 593, 2018.
  * [3] M. J. Osborne and A. Rubinstein, _A course in game theory_. MIT press, 1994.
  * [4] T. Roughgarden, “Algorithmic game theory,” _Communications of the ACM_ , vol. 53, no. 7, pp. 78–86, 2010.
  * [5] C. Fiscko, B. Swenson, S. Kar, and B. Sinopoli, “Control of parametric games,” _2019 18th European Control Conference (ECC)_ , pp. 1036–1042, 2019\.
  * [6] L. Buşoniu, R. Babuška, and B. D. Schutter, “Multi-agent reinforcement learning: An overview,” _Innovations in multi-agent systems and applications-1_ , pp. 183–221, 2010.
  * [7] M. Tan, “Multi-agent reinforcement learning: Independent vs. cooperative agents,” in _Proceedings of the tenth international conference on machine learning_ , 1993, pp. 330–337.
  * [8] Y. Yang and J. Wang, “An overview of multi-agent reinforcement learning from game theoretical perspective,” _arXiv preprint arXiv:2011.00583_ , 2020.
  * [9] K. Zhang, Z. Yang, and T. Başar, “Multi-agent reinforcement learning: A selective overview of theories and algorithms,” _Handbook of Reinforcement Learning and Control_ , pp. 321–384, 2021.
  * [10] S. Hendrix. (2016) Traffic-weary homeowners and waze are at war, again. guess who’s winning? [Online]. Available: https://www.washingtonpost.com/local/traffic-weary-homeowners-and-waze-are-at-war-again-guess-whos-winning/2016/06/05/c466df46-299d-11e6-b989-4e5479715b54_story.html
  * [11] L. Plaugic. (2015) Miami cops are falsely reporting their locations on waze to trick drivers. [Online]. Available: https://www.theverge.com/2015/2/12/8025209/waze-miami-cops-false-reporting-google-traffic-app
  * [12] C. Guestrin, D. Koller, and R. Parr, “Multiagent planning with factored mdps.” in _NIPS_ , vol. 1, 2001, pp. 1523–1530.
  * [13] R. Becker, S. Zilberstein, V. Lesser, and C. V. Goldman, “Transition-independent decentralized markov decision processes,” in _Proceedings of the second international joint conference on Autonomous agents and multiagent systems_ , 2003, pp. 41–48.
  * [14] D. Koller and R. Parr, “Policy iteration for factored mdps,” _arXiv preprint arXiv:1301.3869_ , 2013.
  * [15] B. Sallans and G. E. Hinton, “Reinforcement learning with factored states and actions,” _The Journal of Machine Learning Research_ , vol. 5, pp. 1063–1088, 2004.
  * [16] D. Sahabandu, L. Niu, A. Clark, and R. Poovendran, “Scalable planning in multi-agent mdps,” _arXiv preprint arXiv:2103.15894_ , 2021.
  * [17] I. Osband and B. Van Roy, “Near-optimal reinforcement learning in factored mdps.”
  * [18] A. Y. Ng and M. I. Jordan, “Pegasus: A policy search method for large mdps and pomdps,” _arXiv preprint arXiv:1301.3878_ , 2013.
  * [19] T. G. Dietterich, “Hierarchical reinforcement learning with the maxq value function decomposition,” _Journal of artificial intelligence research_ , vol. 13, pp. 227–303, 2000.
  * [20] D. Koller and R. Parr, “Computing factored value functions for policies in structured mdps,” in _IJCAI_ , vol. 99, 1999, pp. 1332–1339.
  * [21] C. Guestrin, D. Koller, R. Parr, and S. Venkataraman, “Efficient solution algorithms for factored mdps,” _Journal of Artificial Intelligence Research_ , vol. 19, pp. 399–468, 2003.
  * [22] C. Fiscko, S. Kar, and B. Sinopoli, “Efficient solutions for targeted control of multi-agent mdps,” in _2021 American Control Conference (ACC)_. IEEE, 2021, pp. 690–696.
  * [23] S. Chaimontree, K. Atkinson, and F. Coenen, “Best clustering configuration metrics: towards multiagent based clustering,” in _International Conference on Advanced Data Mining and Applications_. Springer, 2010, pp. 48–59.
  * [24] A. A. Abbasi and M. Younis, “A survey on clustering algorithms for wireless sensor networks,” _Computer communications_ , vol. 30, no. 14-15, pp. 2826–2841, 2007.
  * [25] A. S. Rostami, M. Badkoobe, F. Mohanna, A. A. R. Hosseinabadi, A. K. Sangaiah _et al._ , “Survey on clustering in heterogeneous and homogeneous wireless sensor networks,” _The Journal of Supercomputing_ , vol. 74, no. 1, pp. 277–323, 2018.
  * [26] A. Krause, R. Rajagopal, A. Gupta, and C. Guestrin, “Simultaneous placement and scheduling of sensors,” in _2009 International Conference on Information Processing in Sensor Networks_. IEEE, 2009, pp. 181–192.
  * [27] D. S. Dos Santos and A. L. Bazzan, “Distributed clustering for group formation and task allocation in multiagent systems: A swarm intelligence approach,” _Applied Soft Computing_ , vol. 12, no. 8, pp. 2123–2131, 2012.
  * [28] M. Brambilla, E. Ferrante, M. Birattari, and M. Dorigo, “Swarm robotics: a review from the swarm engineering perspective,” _Swarm Intelligence_ , vol. 7, no. 1, pp. 1–41, 2013.
  * [29] E. Ferrara, M. JafariAsbagh, O. Varol, V. Qazvinian, F. Menczer, and A. Flammini, “Clustering memes in social media,” in _2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013)_. IEEE, 2013, pp. 548–555.
  * [30] F. D. Malliaros and M. Vazirgiannis, “Clustering and community detection in directed networks: A survey,” _Physics reports_ , vol. 533, no. 4, pp. 95–142, 2013.
  * [31] L. Zhao, H. Nagamochi, and T. Ibaraki, “Greedy splitting algorithms for approximating multiway partition problems,” _Mathematical Programming_ , vol. 102, no. 1, pp. 167–183, 2005.
  * [32] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions—i,” _Mathematical programming_ , vol. 14, no. 1, pp. 265–294, 1978.
  * [33] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, “Maximizing a submodular set function subject to a matroid constraint,” in _International Conference on Integer Programming and Combinatorial Optimization_. Springer, 2007, pp. 182–196.
  * [34] L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko, “Tight approximation algorithms for maximum general assignment problems,” in _Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm_ , 2006, pp. 611–620.
  * [35] D. P. Bertsekas, D. P. Bertsekas, D. P. Bertsekas, and D. P. Bertsekas, _Dynamic programming and optimal control_. Athena scientific Belmont, MA, 1995, vol. 1, no. 2.
  * [36] M. L. Littman, T. L. Dean, and L. P. Kaelbling, “On the complexity of solving markov decision problems,” _arXiv preprint arXiv:1302.4971_ , 2013.