# Online Selection of Diverse Committees111A short version of this paper
appears in the Proceedings of IJCAI-2021.

Virginie Do1,2222Contact Author<EMAIL_ADDRESS>Jamal Atif1 Jérôme
Lang1&Nicolas Usunier2
1LAMSADE, Université PSL, Université Paris-Dauphine, CNRS, France
2Facebook AI Research

###### Abstract

Citizens’ assemblies need to represent subpopulations according to their
proportions in the general population. These large committees are often
constructed in an online fashion by contacting people, asking for the
demographic features of the volunteers, and deciding to include them or not.
This raises a trade-off between the number of people contacted (and the
incurring cost) and the representativeness of the committee. We study three
methods, theoretically and experimentally: a greedy algorithm that includes
volunteers as long as proportionality is not violated; a non-adaptive method
that includes a volunteer with a probability depending only on their features,
assuming that the joint feature distribution in the volunteer pool is known;
and a reinforcement learning based approach when this distribution is not
known a priori but learnt online.

##  1 Introduction

Forming a representative committee consists in selecting a set of individuals,
who agree to serve, in such a way that every part of the population, defined
by specific features, is represented proportionally to its size. As a
paradigmatic example, the Climate Assembly in the UK and the Citizens’
Convention for Climate in France brought together 108 and 150 participants
respectively, representing sociodemographic categories such as gender, age,
education level, professional activity, residency, and location, in proportion
to their importance in the wider society. Beyond citizens’ deliberative
assemblies, proportional representation often has to be respected when forming
an evaluation committee, selecting a diverse pool of students or employees,
and so on.

Two key criteria for evaluating the committee formation process are the
representativeness of the final selection and the number of persons contacted
(each of these incurring a cost). The trade-off is that the higher the number
of people contacted, the more proportional the resulting committee.

A first possibility is to use an offline strategy (as for the UK assembly):
invitations are sent to a large number of people (30,000), and the final group
is selected among the pool of volunteers. An alternative setting which is
common in hiring is to consider an online process: the decision-maker is given
a stream of candidates and has to decide at each timestep whether or not to
admit the candidate to the final committee. This work focuses on the latter
setting.

A further difficulty is that the distribution of _volunteers_ is not
necessarily known in advance. For example, although the target is to represent
distinct age groups proportionally to their distribution in the wider
population, it may be the case that older people are predominant among
volunteers.

Multi-attribute proportional representation in committee selection in an off-
line setting usually assumes full access to a finite (typically large)
database of candidates. This assumption is impractical in a variety of real-
world settings: first, the database does not exist beforehand and constructing
it would require contacting many more people than necessary; second, in some
domains, the decision to hire someone should be made immediately so that
people don’t change their mind in the meantime (which is typical in
professional contexts).

An online strategy must achieve a good trade-off between sample complexity,
i.e. the number of timesteps needed to construct a full committee, and the
quality of the final committee, as measured by its distance to the target
distribution.

We focus on the online setting. We introduce a new model and offer three
different strategies, which rely on different assumptions on the input (and
the process). The greedy strategy selects volunteers as long as their
inclusion does not jeopardize the size and representation constraints; it does
not assume any prior distribution on the volunteer pool. The nonadaptive
strategy, based on constrained Markov decision processes, repeatedly chooses a
random person, and decides whether to include or not a volonteer with a
probability that depends only on their features; it assumes the joint
distribution in the volunteer pool is known; it can be parallelised. Finally,
the reinforcement learning strategy assumes this distribution is not known a
priori but can be learnt online.

Which of these strategies are interesting depends on domain specificities. For
each, we study bounds for expected quality and sample complexity, and perform
experiments using real data from the UK Citizens’ Assembly on Brexit.

The outline of the paper is as follows. We discuss related work in Section 2,
define the problem in Section 3, define and study our three strategies in
Sections 3.2, 4 and 5, analyse our experiments in Section 6 and conclude in
Section 7.

##  2 Related work

#### Diversity and representation in committee (s)election

The problem of selecting a diverse set of candidates from a candidate
database, where each candidate is described by a vector of attribute values,
has been considered in several places. In Lang and Skowron (2018), the goal is
to find a committee of a fixed size whose distribution of attribute values is
as close as possible to a given target distribution. In Celis et al. (2018);
Bredereck et al. (2018), each candidate has a score, obtained from a set of
votes, and some constraints on the proportion of selected candidates with a
given attribute value are specified; the goal is to find a fixed-size
committee of maximal score satisfying the constraints. In the same vein, Aziz
(2019) considers soft constraints, and Bei et al. (2020) do not require the
size of the committee to be fixed.333 Note that diversity and proportional
representation are often used with a different meaning in multiwinner
elections, namely, in the sense that each voter should feel represented in an
elected committee, regardless of attributes. A good entry to this literature
is the survey Faliszewski et al. (2017).

Our online setting shifts the difficulty of the multi-attribute representation
problem from computational complexity analyses, to the need for probabilistic
guarantees on the tradeoffs between sample complexity and achieved
proportionality.

#### Representative and fair sortition

Finding a representative committee (typically, a panel of citizens) with
respect to a set of attributes, using sortition, is the topic of at least two
recent papers. Benadè et al. (2019) show that stratification (random selection
from small subgroups defined by attribute values, rather than from the larger
group) only helps marginally. Flanigan et al. (2020) go further and consider
this three-stage selection process: (1) letters are sent to a large number of
random individuals (the recipients); (2) these recipients answer whether they
agree to participate, and if so, give their features; those individuals
constitute the pool; (3) a sampling algorithm is used to select the final
panel from the pool. As the probability of willingness to participate is
different across demographic groups, each person is selected with a
probability that depends on their features, so as to correct this self-
selection bias. This guarantees that the whole process be fair to all
individuals of the population, with respect of going from the initial
population to the panel.444Fairness guarantees are pushed further in following
(yet unpublished) work by the authors: see https://youtu.be/x_1Ce1kT7vc.

The main differences between this work and ours are: (1) (once again) our
process is online; (2) we do not consider individual fairness, only group
representativeness; (3) we care about minimizing the number of people
contacted. Moreover, unlike off-line processes, our process can be applied in
contexts where hiring a person just interviewed cannot be delayed; this may
not be crucial for citizens’ assemblies (although someone who volunteers at
first contact may change their mind if the delay until the final selection is
long), but this is definitely so when hiring a diverse team of employees.

#### Online selection problems

Generalized secretary problems Babaioff et al. (2008) are optimal stopping
problems where the goal is to hire the best possible subset of persons,
assuming that persons arrive one at a time, their value is observed at that
time, and the decision to hire or not them must be taken immediately. The
problem has been generalized to finding a set of items maximizing a submodular
value function Bateni et al. (2013); Badanidiyuru et al. (2014) While the
latter models do not deal with diversity constraints, Stoyanovich et al.
(2018) aims at selecting a group of people arriving in a streaming fashion
from a finite pool, with the goal of optimizing their overall quality subject
to diversity constraints. The common point with our approach is the online
nature of the selection process. The main differences are that they consider
only one attribute, the size of the pool is known, and yet more importantly,
what is optimized is the intrinsic quality values of the candidates and not
the number of persons interviewed. Closer to our setting is Panigrahi et al.
(2012) who consider diversity along multiple features in online selection of
search results, regardless of item quality. They only seek to maximise
diversity, and do not consider trade-offs with the number of items observed.

The diverse hiring setting of Schumann et al. (2019) is very different. At
each time step, the decision-maker chooses which candidate to interview and
only decides on which subset to hire after multiple rounds, whereas in our
setting, candidates arrive one by one and decisions are made immediately.

##  3 Formal setting

###  3.1 Problem definition

Let $\mathcal{X}=\mathcal{X}_{1}\times...\times\mathcal{X}_{d}$ be the product
space of $d$ finite domains, each of size $D_{i}=|\mathcal{X}_{i}|$, and where
we identify $\mathcal{X}_{i}$ with $[D_{i}]=\\{1,...,D_{i}\\}$. Each candidate
is represented by a _characteristic vector_ $x\in\mathcal{X}$ with $d$
_features_. Let $x^{i}\in\mathcal{X}_{i}$ denote the value of the $i$-th
feature. For each $i\in[d]$, we consider a _target vector_
$\rho^{i}\in(0,1)^{D_{i}}$ with $\sum_{j=1}^{D_{i}}\rho_{j}^{i}=1.$

The candidate database is infinite and the horizon as well. At each timestep
$t\geq 1$, the agent observes a candidate $x_{t}$ drawn i.i.d. from a
stationary distribution $p$ over $\mathcal{X}$, i.e. $x_{t}\sim p$. The
decision-maker must immediately decide between two actions: _accept_ or
_reject_ the candidate, which we respectively denote as $a_{t}=1$ and
$a_{t}=0$.

The goal is to select a _committee_ $C$ of $K$ candidates that matches the
target vectors as closely as possible, while minimizing the number of
candidates screened.

For some set $C$, let $\lambda(C)\in\prod_{i=1}^{d}[0,1]^{D_{i}}$ be the
_representation profile_ of $C$, where $\lambda_{j}^{i}(C)=\frac{|\\{x\in
C:x^{i}=j\\}|}{|C|}$. We define the _representation loss_ as
$\|\lambda(C)-\rho\|_{\infty}=\max_{i\in[d],j\in[D_{i}]}|\lambda_{j}^{i}(C)-\rho_{j}^{i}|$.
We evaluate how much $C$ matches the target $\rho$ by the $\ell_{\infty}$
metric, because it is harsher than $\ell_{1},\ell_{2}$ on committees that are
unacceptable in our applications (e.g. committees with no women that achieve
perfect representation on all other categories than gender).

Let $C_{t}=\\{x_{t^{\prime}}:t^{\prime}\leq t,a_{t^{\prime}}=1\\}$ denote the
set of all accepted candidates at the end of step $t$. The agent stops at
$\tau$, where $\tau$ is the first time when $K$ candidates have been accepted,
i.e. the total number of candidates screened. The agent following a (possibly
randomized) algorithm $ALG$ must minimize the _sample complexity_
$\mathbb{E}^{p,ALG}[\tau]$.

Importantly, we consider two settings: whether the candidate distribution $p$
is _known_ or _unknown_.

######  Remark.

In this model, we simply ignore non-volunteers, since the agent only needs to
make decisions for volunteers, which from now on we call _candidates_. The
joint distribution of characteristic vectors in the population of candidates
is $p$.

###  3.2 Greedy strategy

We describe a first simple strategy. In Greedy, the agent greedily accepts any
candidate as long as the number of people in the committee with $x^{i}=j$ does
not exceed the quota $\lceil\rho_{j}^{i}K\rceil+\frac{\epsilon K}{(D_{i}-1)}$
for any $i,j$, where $\epsilon>0$ is some tolerance parameter for the
representation quality.

######  Proposition 1.

The representation loss incurred by Greedy is bounded as follows:

$\displaystyle\|\lambda(C_{\tau})-\rho\|_{\infty}\mathop{\leq}_{a.s.}\big{(}\frac{\max_{i\in[d]}D_{i}-1}{K}+\epsilon).$

The proof and pseudocode are included in App. A.

This method is simple to interpret and implement, and can even be used when
the candidate distribution $p$ is unknown. However, in the following example,
we see that Greedy may be inefficient because it requires interacting with an
arbitrarily large number of candidates to recruit a full committee.

gender \ age | S | J
---|---|---
M | $\nicefrac{{1}}{{2}}-\epsilon^{\prime}$ | $\nicefrac{{1}}{{4}}$
F | $\nicefrac{{1}}{{4}}$ | $\epsilon^{\prime}$
Table 1: Example candidate distribution $p$ with 2 binary features.

######  Example 1.

Let $\epsilon^{\prime}>0,\ll 1$. There are 2 binary features, _gender_ and
_age_ , with domains $\mathcal{X}_{\text{gender}}=\\{M,F\\}$ and
$\mathcal{X}_{\text{age}}=\\{S,J\\}$. The candidates are distributed as $p$
given in Table 1. We want a committee of size $K=4$ (e.g., a thesis committee)
and the target is
$\rho^{\text{gender}}=(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$ and
$\rho^{\text{age}}=(\nicefrac{{3}}{{4}},\nicefrac{{1}}{{4}})$.

Let $A$ be the event that in the first $3$ timesteps, the agent observes
candidates with characteristic vectors $\\{FS,MS,MS\\}$ in any order. Then
Greedy accepts all of them, i.e. $A=\left\\{C_{3}=\\{FS,MS,MS\\}\right\\}$. We
have:
$\mathbb{P}\left[{A}\right]=\nicefrac{{1}}{{4}}(\nicefrac{{1}}{{2}}-\epsilon^{\prime})^{2}\times
3!=\nicefrac{{3}}{{2}}(\nicefrac{{1}}{{2}}-\epsilon^{\prime})^{2}\geq\nicefrac{{3}}{{2}}\big{(}\nicefrac{{1}}{{3}}\big{)}^{2}=\nicefrac{{1}}{{6}}$.

Under event $A$, Greedy can only stop upon finding $FJ$ in order to satisfy
the representation constraints. Therefore, $\tau|A$ follows a geometric
distribution with success probability $\epsilon^{\prime}$, hence its
expectation is $\nicefrac{{1}}{{\epsilon^{\prime}}}$, and
$\mathbb{E}^{p,\texttt{Greedy}}[\tau]\geq\mathbb{E}\left[{\tau|A}\right]\times\mathbb{P}\left[{A}\right]=\nicefrac{{1}}{{6\epsilon^{\prime}}}.$
Therefore, the sample complexity of Greedy in this example is arbitrarily
large.

This example shows the limits of directly applying a naive strategy to our
online selection problem, where the difficulty arises from considering
multiple features simultaneously, even when there are only $2$ binary
features. We further discuss the strengths and weaknesses of Greedy, and its
sensitivity to the tolerance $\epsilon$ in our experiments in Section 6.

The greedy strategy is adaptive, in the sense that decisions are made based on
the current candidate and candidates accepted in the past. In the following
section, we present, with theoretical guarantees, an efficient yet non-
adaptive algorithm based on constrained MDPs for the setting in which the
candidate distribution is known. We then adapt this approach to the case when
this distribution is unknown, using techniques for efficient exploration /
exploitation in constrained MDPs relying on the principle of optimism in the
face of uncertainty.

##  4 $p$ is known: constrained MDP strategy

In this section, we assume the distribution $p$ is known, and we place
ourselves in the limit where we would select a committee of infinite size, and
aim to maximize the rate at which candidates are selected, under the
constraint that the proportion of accepted candidates per feature value is
controlled by $\rho$. One advantage of this approximation is that the optimal
policy is stationary, thus simple to represent. Moreover, as stationary
policies can be very well parallelized, in the case where multiple candidates
can be interviewed simultaneously. To apply this approach to the finite-size
committee selection problem, one needs to interrupt the agent when $K$
candidates have been selected. We showcase a high probability bound of
$O(\sqrt{1/K})$ on the representation loss, which guarantees that for large
enough values of $K$, the resulting committee is representative.

From now on, we assume that any feature vector can be observed, i.e., $p(x)>0$
for all $x$, so that proportional representation constraints can be satisfied.

###  4.1 Our model

Fundamentally, our problem could be seen as a contextual bandit with
stochastic contexts $x_{t}\sim p$ and two actions $a_{t}=0$ or $1$. However,
the type of constraints incurred by proportional representation are well
studied in constrained MDPs (CMDPs) Altman (1999), whereas the contextual
bandits literature focused on other constraints (e.g., knapsack constraints
Agrawal and Devanur (2016)). We show how we can efficiently leverage the CMDP
framework for our online committee selection problem.

Formally, we introduce an MDP $M=(\mathcal{X},\mathcal{A},P,r)$, where the set
of states is the $d$-dimensional candidate space $\mathcal{X}$, the set of
actions is $\mathcal{A}=\\{0,1\\}$, and the (deterministic) reward is
$r(x,a)=\mathds{1}_{\\!\\{a=1\\}}$. The transition kernel $P$, which defines
the probability to be in state $x^{\prime}$ given that the previous state was
$x$ and the agent took action $a$, is very simple in our case: we simply have
$P(x^{\prime}|x,a)=p(x^{\prime})$ since candidates are drawn i.i.d regardless
of the previous actions and candidates.

We consider the _average reward_ setting in which the performance of a policy
$\pi:\mathcal{X}\times\mathcal{A}\rightarrow[0,1]$ is measured by its _gain_
$g^{p,\pi}$, defined as:

$\displaystyle
g^{p,\pi}(x)=\lim_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}^{p,\pi}\left[\sum_{t=1}^{T}r(x_{t},a_{t})\bigg{|}x_{1}=x\right].$

We simply write $g^{p,\pi}:=g^{\pi}$ when the underlying transition is $p$
without ambiguity.

We include proportional representation constraints following the framework of
CMDPs, where the set of allowed policies is restricted by a set of additional
constraints specified by reward functions. In our case, for
$i\in[d],j\in[D_{i}]$, we introduce
$r_{j}^{i}(x,a)=\mathds{1}_{\\!\\{x^{i}=j,a=1\\}}$, and let
$\xi_{j}^{i}=r_{j}^{i}-\rho_{j}^{i}r$ be the reward function for the
constraint indexed by $i,j$. Similarly to the gain, we define
${h_{j}^{i}}^{\pi}=\lim_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}^{\pi}\left[\sum_{t=1}^{T}\xi_{j}^{i}(x_{t},a_{t})\right]$.
The CMDP is defined by:

$\displaystyle\max_{\pi}\\{g^{\pi}\,|\,\forall i\in[d],\forall
j\in[D_{i}],{h_{j}^{i}}^{\pi}=0\\}.$ (1)

Given the simplicity of the transition kernel, and since the MDP is ergodic by
the assumption $p>0$, the gain is constant, i.e. $\forall
x\in\mathcal{X},g^{\pi}(x)=g^{\pi}$, and problem (1) is well defined. From now
on, we only write $g^{\pi}$ and ${\xi_{j}^{i}}^{\pi}$. Moreover, the optimal
policy for the CMDP (1) is denoted $\pi^{*}$ and is _stationary_ Altman
(1999).

######  Lemma 1.

$g^{\pi}$ is the _selection rate_ under policy $\pi$:

$\displaystyle g^{\pi}=\sum_{x}p(x)\pi(x,1)=\mathbb{P}^{p,\pi}[a=1]$

Moreover, if $\pi$ is feasible for CMDP (1), then:

$\displaystyle\forall i\in[d],\forall
j\in[D_{i}],\mathbb{P}^{p,\pi}[x^{i}=j|a=1]=\rho_{j}^{i}.$

Lemma 1 implies that (a) $\pi^{*}$ maximises the selection rate of candidates,
and (b) the constraints of (1) force candidates $x$ with $x^{i}=j$ to be
accepted in proportions given by $\rho_{j}^{i}$.

The CMDP can be expressed as the linear program:

$\displaystyle\max_{\pi\in\mathbb{R}_{+}^{\mathcal{X}\times\mathcal{A}}}$
$\displaystyle\sum_{x,a}\pi(x,a)p(x)r(x,a)$ (2) u.c. $\displaystyle\forall
x\in\mathcal{X},\sum_{a}\pi(x,a)=1$ $\displaystyle\forall
i,j,\sum_{x,a}\pi(x,a)p(x)\xi_{j}^{i}(x,a)=0.$

Notice that problem (2) is feasible by the assumption that $\forall
x\in\mathcal{X},p(x)>0$. Next we study how well the proportional selection
along features is respected when we shift from infinite to finite-sized
committee selection.

###  4.2 Theoretical guarantees

We analyze the CMDP-based strategy where at each timestep, the agent observes
candidates $x_{t}\sim p$, decides to accept $x_{t}$ by playing
$a_{t}\sim\pi^{*}(.|x_{t})$ and stops when $K$ candidates have been accepted.
We later refer to it as CMDP for brevity.

First, we formally relate the gain $g^{\pi}$ that we optimize for in (1) to
the quantity of interest $\mathbb{E}^{p,\pi}[\tau]$.

######  Lemma 2.

For any stationary policy $\pi$, $\mathbb{E}^{p,\pi}[\tau]=\frac{K}{g^{\pi}}$.

Lemma 2 is a direct consequence of the fact that $\tau+K$ follows a negative
binomial distribution with parameters $K$ and $1-g^{\pi}$, which are
respectively the number of successes and the probability of failure, i.e. of
rejecting a candidate under $\pi$. Note that this is only true because in our
case the transition structure of the MDP ensures constant gain. A quick sanity
check shows that if the agent systematically accepts all candidates, i.e.
$g^{\pi}=1$, then $\mathbb{E}^{p,\pi}[\tau]=K$, and that maximizing $g^{\pi}$
is equivalent to minimizing $\mathbb{E}^{p,\pi}[\tau]$.

We exhibit a bound on the representation loss of CMDP which follows the
optimal stationary policy $\pi^{*}$ of CMDP (1). Let
$\tilde{d}=\sum_{i=1}^{d}(D_{i}-1).$ ($\tilde{d}=d$ when all features are
binary.)

######  Proposition 2.

Let $\pi^{*}$ be an optimal stationary policy for CMDP (1). Let $\delta>0$.
Then,

$\displaystyle\mathbb{P}^{p,\pi^{*}}\left[\|\lambda(C_{\tau})-\rho\|_{\infty}\leq\sqrt{\frac{\log(\frac{2\tilde{d}}{\delta})}{2K}}\right]\geq
1-\delta.$

All proofs of this section are available in Appendix B.1.

The upper bound on the representation loss of CMDP decreases with the
committee size in $\sqrt{1/K}$. This shows that the stationary policy
$\pi^{*}$ works well for larger committees, although it acts independently
from previously accepted candidates. The intuition is that for larger
committees, adding a candidate has less impact on the current representation
vector.

######  Example 2.

We take the same attributes and same distribution as in Table 1, with
$\epsilon^{\prime}=\nicefrac{{1}}{{6}}$. Here, the target vectors are
$\rho^{\text{gender}}=(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$ and
$\rho^{\text{age}}=(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$: an ideal
committee contains as many women as men, as many senior as junior.

With the optimal policy for LP (2), each time the current volunteer is a
senior male, we select him with probability $\nicefrac{{1}}{{2}}$; all other
volunteers are selected with probability 1. The expected final composition of
the pool is 30% of junior male, 30% of senior female, 20% of junior female and
20% of senior male. As the policy selects in average $\nicefrac{{5}}{{6}}$ of
the volunteers, the expected time until we select $K$ candidates is
$\mathbb{E}^{p,\pi^{*}}[\tau]=(\nicefrac{{6}}{{5}})K$. More details can be
found in App. E.

##  5 $p$ is unknown: optimistic CMDP strategy

input : confidence $\delta$, committee size $K$, targets $\rho$

output : committee $C_{\tau}$

1 $t\leftarrow 0$, $C_{0}\leftarrow\emptyset$;

2 while  _$|C_{t}| <K$ _ do

3 for  _episode $l=1,2,...$_ do

4 $\tau_{l}=t+1$;

5 $\pi_{l}\leftarrow$ sol. of (4) via the extended LP (5);

6 while  _$n_{t}(x_{t}) <2n_{\tau_{l}-1}(x_{t})$_ do

7 $t\leftarrow t+1$, Execute $\pi_{l}$;

8

9 end while

10

11 end for

12

13 end while

return _$C_{t}$_

Algorithm 1 RL-CMDP algorithm.

We now tackle the committee selection problem when the candidate distribution
$p$ is unknown and must be learned online. Let $g^{*}=g^{\pi^{*}}$ be the
value of (1), which is the optimal gain of the CMDP when the distribution $p$
is known. We evaluate a learning algorithm by:

  1. 1.

the performance regret: $R(T)=\sum_{t=1}^{T}(g^{*}-r(x_{t},a_{t}))$,

  2. 2.

the cost of constraint violations:

$R^{c}(T)=\max_{i,j}\big{|}\sum_{t=1}^{T}\xi_{j}^{i}(x_{t},a_{t})\big{|}$.

We propose an algorithm that we call RL-CMDP (Reinforcement Learning in CMDP,
Alg. 1). It is an adaptation of the _optimistic_ algorithm UCRL2 Jaksch et al.
(2010), and it also builds on the algorithm OptCMDP proposed by Efroni et al.
(2020) for finite-horizon CMDPs. Learning in average-reward CMDPs involves
different challenges, because there is no guarantee that the policy at each
episode has constant gain. It does not matter in our case, since as we noted
in Sec. 4, the simple structure of the transition kernel ensures constant
gain, and does not require to use the Bellman equation. The few works on
learning in average-reward CMDPs make unsuitable assumptions for our setting
Zheng and Ratliff (2020); Singh et al. (2020).

RL-CMDP proceeds in episodes, which end each time the number of observations
for some candidate $x$ doubles. During each episode $l$, observed candidates
$x_{t}$ are accepted on the basis of a single stationary policy $\pi_{l}$.

Let $\tau_{l}$ denote the start time of episode $l$ and
$E_{l}=[\tau_{l},\tau_{l+1}]$. Let
$n_{t}(x)=\sum_{t^{\prime}=1}^{t}\mathds{1}_{\\!\\{x_{t^{\prime}}=x\\}}$ and
$N(t)=|C_{t-1}|=\sum_{t^{\prime}=1}^{t-1}\mathds{1}_{\\!\\{a_{t^{\prime}}=1\\}}$.
Let
$N_{j}^{i}(t)=\sum_{t^{\prime}=1}^{t-1}\mathds{1}_{\\!\\{x^{i}_{t^{\prime}}=j,a_{t^{\prime}}=1\\}}$
be the number of accepted candidates $x$ such that $x^{i}=j$ before $t$.

At each episode $l$, the algorithm estimates the true candidate distribution
by the empirical distribution
$\hat{p}_{l}(x)=\frac{n_{\tau_{l}-1}(x)}{\tau_{l}-1}$ and maintains confidence
sets $B_{l}$ on $p$. As in UCRL2, these are built using the inequality on the
$\ell_{1}$-deviation of $p$ and $\hat{p}_{l}$ from Weissman et al. (2003):

######  Lemma 3.

With probability $\geq 1-\frac{\delta}{3}$,

$\displaystyle\|\hat{p}_{l}-p\|_{1}\leq\sqrt{\frac{2|\mathcal{X}|\log\big{(}6|\mathcal{X}|\tau_{l}(\tau_{l}-1)/\delta\big{)}}{\tau_{l}-1}}:=\beta_{l}$
(3)

Let
$B_{l}=\\{\tilde{p}\in\Delta(\mathcal{X}):\|\hat{p}_{l}-\tilde{p}\|_{1}\leq\beta_{l}\\}$
be the confidence set for $p$ at episode $l$. The associated set of compatible
CMDPs is then
$\\{\tilde{M}=(\mathcal{X},\mathcal{A},\tilde{p},r,\xi):\tilde{p}\in
B_{l}\\}$. At the beginning of each episode, RL-CMDP finds the optimum of:

$\displaystyle\max_{\pi\in\Pi,\tilde{p}\in
B_{l}}\\{g^{\tilde{p},\pi}\,|\,\forall
i,j,\,{h_{j}^{i}}^{\tilde{p},\pi}=0\\}.$ (4)

#### Extended LP

In order to optimize this problem, we re-write (4) as an extended LP.
Following Rosenberg and Mansour (2019) and the CMDP literature, we introduce
the state-action occupation measure $\mu(x,a)=\pi(x,a)p(x)$ and variables
$\beta(x)$ to linearize the $\ell_{1}$ constraint induced by the confidence
set:

$\displaystyle\max_{\begin{subarray}{c}\mu\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}\\\
\beta\in\mathbb{R}^{\mathcal{X}}\end{subarray}}$
$\displaystyle\sum_{x,a}\mu(x,a)r(x,a)$ (5) u.c. $\displaystyle\mu\geq
0,\sum_{x,a}\mu(x,a)=1$ $\displaystyle\forall
x,\sum_{a}\mu(x,a)\leq\hat{p}_{l}(x)+\beta(x)$ $\displaystyle\forall
x,\sum_{a}\mu(x,a)\geq\hat{p}_{l}(x)-\beta(x)$ $\displaystyle\forall
x,a,\sum_{y}\beta(y)\leq\mu(x,a)\beta_{l}$ $\displaystyle\forall
i,j,\sum_{x,a}\mu(x,a)\xi_{j}^{i}(x,a)=0.$

The last constraint is the proportional representation constraint. The second
to fourth constraints enforce the compatibility of $\mu$ with the $\ell_{1}$
confidence set. We retrieve the distribution as
$\tilde{p}_{l}(x)=\sum_{a}\mu(x,a)$, and the policy as:

$\displaystyle\pi_{l}(x,a)=\begin{cases}\frac{\mu(x,a)}{\tilde{p}_{l}(x)}&\text{if
}\tilde{p}_{l}\neq 0\\\ \frac{1}{2}&\text{otherwise\,.}\end{cases}$

Precisely, if some $\tilde{p}_{l}(x)=0$, we may set the policy $\pi_{l}(a|x)$
arbitrarily. Since the MDP induced by $\tilde{p}$ is still weakly
communicating, and in particular any policy is unichain, the optimal gain in
this CMDP is not affected.

We now provide regret and representativeness guarantees.

######  Theorem 1.

With probability $\geq 1-\delta$, the regret of RL-CMDP satisfies:

$\displaystyle
R(T)=O\big{(}\sqrt{|\mathcal{X}|T\log(|\mathcal{X}|T/\delta)}\big{)}$
$\displaystyle
R^{c}(T)=O\big{(}\sqrt{|\mathcal{X}|T\log(|\mathcal{X}|T/\delta)}\big{)}.$

Moreover, with probability $1-\delta$, the representation loss of RL-CMDP at
horizon $T$ satisfies:

$\displaystyle\|\lambda(C_{T})-\rho\|_{\infty}=O\left(\frac{1}{g^{*}}\sqrt{\frac{|\mathcal{X}|\log\big{(}|\mathcal{X}|T/\delta\big{)}}{T}}\right).$

The full proof is in Appendix B.2. It relies on decomposing regret over
episodes, bounding the error on $p$ which decreases over episodes as the
confidence sets are refined, and leveraging martingale inequalities on the
cumulative rewards.

Since $\frac{R(T)}{T}=g^{*}-\frac{N(T)}{T}$, it means that with high
probability, the difference between the optimal selection rate and the
selection rate of RL-CMDP decreases in $\sqrt{\log(T)/T}$ w.r.t. the horizon
$T$. The representation loss decreases at the same speed, meaning that the
agent should see enough candidates to accurately estimate $p$, and accept
candidates at little cost for representativeness.

Compared to the bound from Proposition 2, the cost of not knowing $p$ on
representativeness is a $\sqrt{|\mathcal{X}|\log(|\mathcal{X}|)}$ factor. This
is due to the estimation of $p$ in the worst case, which is controlled by
Lemma 3. As we show in our experiments (Sec. 6), the impact of $|\mathcal{X}|$
on performance regret (and in turn on sample complexity) is not problematic in
our typical citizens’ assembly scenario: since there are only a handful of
features, our algorithm selects candidates quickly in practice (though
representativeness is weakened by not knowing $p$). For specific structures of
$p$, we obtain bounds with better scaling in $|\mathcal{X}|$, by controlling
each entry of $p$ with Bernstein bounds Maurer and Pontil (2009), instead the
$\ell^{1}$-norm. For completeness, we describe this alternative in Appendix C.

Interestingly, the representation loss is also inversely proportional to
$g^{*}$, the optimal selection rate in the true CMDP. The reason is that the
CMDP constraints do not control the ratios
$\lambda_{j}^{i}(C_{T})=\frac{N_{j}^{i}(T)}{N(T)}$, but $N_{j}^{i}(T)$ instead
(by definition of $R^{c}(T)$ and $\xi_{j}^{i}$). If $N(T)$ is small, i.e. due
to a small selection rate $g$, then
$R_{j}^{i}(T)=|N_{j}^{i}(T)-\rho_{j}^{i}N(T)|$ is small, but not necessarily
$|\frac{N_{j}^{i}(T)}{N(T)}-\rho_{j}^{i}|$: the committee is too small to be
representative.

##  6 Experiments

The goal of these experiments is to answer the following: (Q1) In practice,
for which range of committee sizes do our strategies achieve satisfying sample
complexity and representation loss? (Q2) What is the cost of not knowing the
distribution $p$ for the sample complexity and representation loss?

#### Experimental setting

To answer these questions, we use summary data from the 2017 Citizens’
Assembly on Brexit. The participants were recruited in an offline manner:
volunteers could express interest in a survey, and then $53$ citizens were
drawn from the pool of volunteers using stratified sampling, in order to
construct an assembly that reflects the diversity of the UK electorate. We use
summary statistics published in the report Renwick et al. (2017) to simulate
an online recruitment process.

There are $d=6$ features: the organisers expressed target quotas for 2
ethnicity groups, 2 social classes, 3 age groups, 8 regions, 2 gender groups
and 2 Brexit vote groups (remain, leave). The report also includes the number
of people contacted per feature group (e.g., women, or people who voted to
remain) and the volunteering rate for each feature group, which we use as
probability of volunteering given a feature group. We use Bayes’ rule to
compute the probabilities of feature groups among volunteers, and use them as
the marginal distributions $\Pr[x^{i}=j|\text{volunteers}]$ (since we only
consider the population of volunteers). Since we only have access to the
marginals, we compute the joint distribution as if the features were
independent, although our model is agnostic to the dependence structure of the
joint distribution. In Appendix D.2, we present additional experiments with
non-independent features, using a real dataset containing demographic
attributes. The results are qualitatively similar.

We study Greedy with tolerance $\epsilon=0.02,0.05$. We run experiments for
$K=50,100,150,250,500,1000$, averaged over $50$ simulations. More details are
found in App. D.1.

#### (A1)

We compare Greedy and CMDP, when the distribution $p$ is _known_. Figure 1
shows that the greedy strategy with $\epsilon=0.05$ requires $10$ times more
samples than CMDP, and its representation loss is higher as soon as $K\geq
250.$ Greedy with lower tolerance $\epsilon=0.02$ achieves better
representation than CMDP for smaller committees ($K\leq 100$), but the margin
quickly decreases with $K$. However, even for small committees, it requires
about $100$ times more samples, which is prohibitively expensive. Figure 1
shows that for CMDP, the sample complexity grows linearly in the committee
size, with a reasonable slope (we need to find $\tau\approx 500$ volunteers
for a committee of size $K\approx 200$).

#### (A2)

To corroborate the previously discussed effect of $|\mathcal{X}|$ when $p$ is
_unknown_ , we evaluate RL-CMDP on different configurations: (1) using only
the features ethnicity, social class, and gender ($d=3,|\mathcal{X}|=8$), (2)
using all features except regions ($d=5,|\mathcal{X}|=48$). Fig. 2 shows that
unlike CMDP which has full knowledge of $p$, it is for large committee sizes
that RL-CMDP reaches low representation loss (below $0.05$ for $K\geq 1500$ in
the configuration(1)). This is because RL-CMDP needs to collect more samples
to estimate $p$, as discussed in Th. 1. For known $p$, the CMDP approach
achieves the same representativeness for middle-sized committees (repr. loss
$\leq 0.05$ for $K\approx 250$). Hence, comparing the cases of known (Fig. 1)
and unknown distribution $p$ (Fig. 2), the ignorance of $p$ is not costly for
sample complexity, but rather for the representation loss which decreases more
slowly.

Consistently with Th. 1, we observe that the representation loss is higher
when $\mathcal{X}$ is larger ($d=5$). For small and middle-sized committees,
the loss of RL-CMDP is much worse than Greedy’s which also works for unknown
$p$. For large committees though, the margin is only $0.05$ when $K\gtrsim
2000$ and $\tau\approx 3500$ for RL-CMDP (which is $\times 3$ more sample
efficient than Greedy). In absolute terms, the theoretical regret bounds have
a large constant $\sqrt{|\mathcal{X}|}$. This constant is likely unavoidable
asymptotically because it comes from Lem. 3, but our experiments suggest that
in the non-asymptotic regime, RL-CMDP performs better than the bound suggests.

Figure 1: Effect of committee size $K$ on sample complexity and representation
loss for different strategies, in the UK Brexit Assembly experiment, using all
features. $p$ is known.  Figure 2: Effect of committee size $K$ on sample
complexity and representation loss for RL-CMDP, on data simulated from the UK
Brexit Assembly, using $3$ and $5$ features. $p$ is unknown.

##  7 Conclusion

We formalised the problem of selecting a diverse committee with multi-
attribute proportional representation in an online setting. We addressed the
case of known candidate distributions with constrained MDPs, and leveraged
exploration-exploitation techniques to address unknown distributions.

## Acknowledgements

This work was funded in part by the French government under management of
Agence Nationale de la Recherche as part of the “Investissements d’avenir”
program ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We thank Matteo Pirotta for
his helpful suggestions and feedback.

## References

  * Agrawal and Devanur [2016] Shipra Agrawal and Nikhil Devanur.  Linear contextual bandits with knapsacks.  In Advances in Neural Information Processing Systems, pages 3450–3458, 2016.
  * Altman [1999] Eitan Altman.  Constrained Markov decision processes, volume 7.  CRC Press, 1999.
  * Aziz [2019] Haris Aziz.  A rule for committee selection with soft diversity constraints.  Group Decision and Negotiation, 28:1193–1200, 2019.
  * Babaioff et al. [2008] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg.  Online auctions and generalized secretary problems.  ACM SIGecom Exchanges, 7(2):1–11, 2008.
  * Badanidiyuru et al. [2014] Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause.  Streaming submodular maximization: Massive data summarization on the fly.  In Proceedings of the 20th ACM SIGKDD, pages 671–680, 2014.
  * Bateni et al. [2013] MohammadHossein Bateni, Mohammadtaghi Hajiaghayi, and Morteza Zadimoghaddam.  Submodular secretary problem and extensions.  ACM Transactions on Algorithms (TALG), 9(4):1–23, 2013.
  * Bei et al. [2020] Xiaohui Bei, Shengxin Liu, Chung Keung Poon, and Hongao Wang.  Candidate selections with proportional fairness constraints.  In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20, Auckland, New Zealand, May 9-13, 2020, pages 150–158, 2020.
  * Benadè et al. [2019] Gerdus Benadè, Paul Gölz, and Ariel D Procaccia.  No stratification without representation.  In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 281–314, 2019.
  * Bredereck et al. [2018] Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner, and Piotr Skowron.  Multiwinner elections with diversity constraints.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * Celis et al. [2018] L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi.  Multiwinner voting with fairness constraints.  In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 144–151, 2018.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.
  * Efroni et al. [2020] Yonathan Efroni, Shie Mannor, and Matteo Pirotta.  Exploration-exploitation in constrained mdps.  arXiv preprint arXiv:2003.02189, 2020.
  * Faliszewski et al. [2017] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon.  Multiwinner voting: A new challenge for social choice theory.  Trends in computational social choice, 74:27–47, 2017.
  * Flanigan et al. [2020] Bailey Flanigan, Paul Gölz, Anupam Gupta, and Ariel D Procaccia.  Neutralizing self-selection bias in sampling for sortition.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6528–6539. Curran Associates, Inc., 2020.
  * Hoeffding [1994] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In The Collected Works of Wassily Hoeffding, pages 409–426. Springer, 1994.
  * Jaksch et al. [2010] Thomas Jaksch, Ronald Ortner, and Peter Auer.  Near-optimal regret bounds for reinforcement learning.  Journal of Machine Learning Research, 11(4), 2010.
  * Lang and Skowron [2018] Jérôme Lang and Piotr Skowron.  Multi-attribute proportional representation.  Artificial Intelligence, 263:74–106, 2018.
  * Maurer and Pontil [2009] Andreas Maurer and Massimiliano Pontil.  Empirical bernstein bounds and sample variance penalization.  arXiv preprint arXiv:0907.3740, 2009.
  * Panigrahi et al. [2012] Debmalya Panigrahi, Atish Das Sarma, Gagan Aggarwal, and Andrew Tomkins.  Online selection of diverse results.  In Proceedings of the fifth ACM international conference on Web search and data mining, pages 263–272, 2012.
  * Renwick et al. [2017] A Renwick, S Allan, W Jennings, R McKee, M Russell, and G Smith.  A considered public voice on brexit: The report of the citizens’ assembly on brexit.  2017\.
  * Rosenberg and Mansour [2019] Aviv Rosenberg and Yishay Mansour.  Online convex optimization in adversarial markov decision processes.  arXiv preprint arXiv:1905.07773, 2019.
  * Schumann et al. [2019] Candice Schumann, Samsara N Counts, Jeffrey S Foster, and John P Dickerson.  The diverse cohort selection problem.  In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 601–609. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
  * Singh et al. [2020] Rahul Singh, Abhishek Gupta, and Ness B Shroff.  Learning in markov decision processes under constraints.  arXiv preprint arXiv:2002.12435, 2020.
  * Stoyanovich et al. [2018] Julia Stoyanovich, Ke Yang, and HV Jagadish.  Online set selection with fairness and diversity constraints.  In Proceedings of the EDBT Conference, 2018.
  * Weissman et al. [2003] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger.  Inequalities for the l1 deviation of the empirical distribution.  Hewlett-Packard Labs, Tech. Rep, 2003.
  * Zanette and Brunskill [2019] Andrea Zanette and Emma Brunskill.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  arXiv:1901.00210, 2019.
  * Zheng and Ratliff [2020] Liyuan Zheng and Lillian J Ratliff.  Constrained upper confidence reinforcement learning.  arXiv preprint arXiv:2001.09377, 2020.

##  Appendix A Details of the algorithms

For precision, we provide the pseudocode of Greedy in Alg. 2, and the CMDP-
based strategy in Alg. 3.

1

input : tolerance $\epsilon$, committee size $K$, targets $\rho$

output : committee $C_{\tau}$

2 $t\leftarrow 0$, $C_{0}\leftarrow\emptyset$;

3 while  _$|C_{t}| <K$_ do

4 $t\leftarrow t+1$;

5 Observe $x_{t}\sim p$;

6 if  _$\forall
i,j,N_{j}^{i}(t)+\mathds{1}_{\\!\\{x^{i}_{t}=j\\}}\leq\lceil\rho_{j}^{i}K\rceil+\frac{\epsilon
K}{D_{i}-1}$_ then

$C_{t}\leftarrow C_{t-1}\cup\\{x_{t}\\}$ ;

// accept $x_{t}$

7 $\forall i,j,\,N_{j}^{i}(t-1)\leftarrow
N_{j}^{i}(t)+\mathds{1}_{\\!\\{x^{i}_{t}=j\\}}$

8 end if

9

10 end while

11return _$C_{t}$_

Algorithm 2 Greedy algorithm.

input : optimal policy $\pi^{*}$ of (1), committee size $K$

output : committee $C_{\tau}$

1 $t\leftarrow 0$, $C_{0}\leftarrow\emptyset$;

2 while  _$|C_{t}| <K$ _ do

3 $t\leftarrow t+1$, observe $x_{t}\sim p$ and play
$a_{t}\sim\pi^{*}(.|x_{t})$ ;

4 if  _$a_{t}=1$_ then $C_{t}\leftarrow C_{t}\cup\\{x_{t}\\}$;

5

6 end while

return _$C_{t}$_

Algorithm 3 CMDP-based strategy.

We also prove the bound on the representation loss of Greedy from Proposition
1 in Section 3.2.

###### Proof.

For all $i,j$, we have by the if-condition and the termination condition:

$\displaystyle\lambda^{i}_{j}(C_{\tau})=\frac{N^{i}_{j}(\tau)}{K}$
$\displaystyle\leq\frac{\lceil\rho^{i}_{j}K\rceil}{K}+\frac{\epsilon}{D_{i}-1}$
$\displaystyle\leq\rho^{i}_{j}+\frac{1}{K}+\frac{\epsilon}{D_{i}-1}$ (6)
$\displaystyle\leq\rho^{i}_{j}+\frac{D_{i}-1}{K}+\epsilon.$ (7)

For $i\in[d]$, for $j_{0}\in[D_{i}]$, we have:

$\displaystyle\rho_{j_{0}}^{i}=1-\sum_{j\neq j_{0}}\rho_{j}^{i}\,,$
$\displaystyle\lambda_{j_{0}}^{i}(C_{\tau})=1-\sum_{j\neq
j_{0}}\lambda_{j}^{i}(C_{\tau}).$

Combining these observations with (6):

$\displaystyle\lambda_{j_{0}}^{i}(C_{\tau})$ $\displaystyle\geq 1-\sum_{j\neq
j_{0}}\big{(}\rho^{i}_{j}+\frac{1}{K}+\frac{\epsilon}{D_{i}-1}\big{)}$
$\displaystyle=1-\sum_{j\neq j_{0}}\rho^{i}_{j}-\frac{D_{i}-1}{K}-\epsilon$
$\displaystyle=\rho_{j_{0}}^{i}-\frac{D_{i}-1}{K}-\epsilon.$

Combining this lower bound with the upper bound (7), we have for all
$i\in[d],j_{0}\in[D_{i}]$,
$\left|\lambda_{j_{0}}^{i}(C_{\tau})-\rho_{j_{0}}^{i}\right|\leq\frac{D_{i}-1}{K}+\epsilon,$
which gives the result.

∎

##  Appendix B Proofs

###  B.1 Proofs of Section 4

Proof of Lemma 1.

###### Proof.

We have:

$\displaystyle\sum_{x,a}\pi(x,a)p(x)r_{j}^{i}(x,a)$
$\displaystyle=\mathbb{E}_{\begin{subarray}{c}x\sim p\\\
a\sim\pi(\cdot|x)\end{subarray}}\left[{r_{j}^{i}(x,a)}\right]$
$\displaystyle=\mathbb{P}^{p,\pi}[a=1,x^{i}=j],$ $\displaystyle\text{and
}\quad
g^{\pi}=\sum_{x,a}\pi(x,a)p(x)r(x,a)=\mathbb{E}_{\begin{subarray}{c}x\sim p\\\
a\sim\pi(.|x)\end{subarray}}\left[{r(x,a)}\right]$
$\displaystyle=\mathbb{P}^{p,\pi}[a=1].$

The ratio of these two quantities is equal to $\rho_{j}^{i}$ by the last
constraint of (2). It is also equal to $\mathbb{P}[x^{i}=j|a=1],$ which gives
the result.

Note that it also holds true for $j=[D_{i}]$, since

$\displaystyle\mathbb{P}[x^{i}=D_{i}|a=1]=1-\sum_{j^{\prime}\in[D_{i}-1]}\mathbb{P}[x^{i}=j^{\prime}|a=1]$
and
$\displaystyle\rho_{D_{i}}^{i}=1-\sum_{j^{\prime}\in[D_{i}-1]}\rho_{j^{\prime}}^{i}.$

∎

Proof of Proposition 2.

###### Proof.

For any $t>0$, we have

$\lambda_{j}^{i}(C_{t})=\frac{\sum_{s=1}^{t}\mathds{1}_{\\!\\{x^{i}_{s}=j,a_{s}=1\\}}}{\sum_{s=1}^{t}\mathds{1}_{\\!\\{a_{s}=1\\}}}.$

and by Lemma 1, we have:

$\mathbb{E}\left[{\mathds{1}_{\\!\\{x^{i}=j\\}}|a=1}\right]=\rho_{j}^{i}.$

Let $\delta^{\prime}>0$. Conditionally on any $T\geq
K,(a_{1},...,a_{T})\in\\{0,1\\}^{T}$ s.t. $a_{1}+...+a_{T}=K$ and $a_{T}=1$,
the draws of $x^{i}_{t}|a_{t}=1$ are independent and thus, by Hoeffding’s
inequality Hoeffding [1994], we have:

$\displaystyle\mathbb{P}\left[{|\lambda_{j}^{i}(C_{T})-\rho_{j}^{i}|\geq\sqrt{\frac{\log(\frac{2}{\delta^{\prime}})}{2N(T)}}\bigg{|}a_{1},...,a_{T}}\right]\geq
1-\delta^{\prime}$
$\displaystyle=\mathbb{P}\left[{|\lambda_{j}^{i}(C_{T})-\rho_{j}^{i}|\geq\sqrt{\frac{\log(\frac{2}{\delta^{\prime}})}{2K}}\bigg{|}a_{1},...,a_{T}}\right].$

Summing up over all such sequences $(a_{1},...,a_{T})$, we obtain that:

$\displaystyle\mathbb{P}\left[{|\lambda_{j}^{i}(C_{\tau})-\rho_{j}^{i}|\geq\sqrt{\frac{\log(\frac{2}{\delta^{\prime}})}{2K}}}\right]\geq
1-\delta^{\prime}.$

The result follows from applying a union bound over all
$i\in[d],j\in[D_{i}-1]$ (there are $\tilde{d}$ such $(i,j)$ pairs) and
choosing $\delta^{\prime}=\delta/\tilde{d}$.

∎

###  B.2 Proof of Theorem 1

The following lemma states a standard and useful inequality, which is similar
to Lem. 19 in Jaksch et al. [2010].

######  Lemma 4.

Recall that $L$ is the random number of episodes ran by RL-CMDP up until
horizon $T$. We have:

$\displaystyle\sum_{l=1}^{L}\frac{|E_{l}|}{\sqrt{\tau_{l}-1}}\leq 2\sqrt{T}.$

###### Proof.

The proof is similar to that of Lem. 13 in Zanette and Brunskill [2019]: we
see $E_{l}$ as the “derivative” of ${\tau_{l}}$. Formally, let us define:

$\displaystyle F(x)=\sum_{l=1}^{\lfloor x\rfloor}|E_{l}|+|E_{\lceil
x\rceil}|(x-\lfloor x\rfloor)$ $\displaystyle f(x):=F^{\prime}(x)=|E_{\lceil
x\rceil}|.$

We first observe that for any integer $l\in\mathbb{N}$, $f(l)=|E_{l}|$ and
$F(l)=\tau_{l}.$ Secondly, we have

$\displaystyle F(x)\leq\sum_{l=1}^{\lfloor x\rfloor}|E_{l}|+|E_{\lceil
x\rceil}|=\sum_{l=1}^{\lceil x\rceil}|E_{l}|=F(\lceil x\rceil),$

and thus:

$\frac{f(\lceil x\rceil)}{\sqrt{F(\lceil x\rceil)-1}}\\\
\leq\frac{f(x)}{\sqrt{F(x)-1}}.$

We derive our bound as follows:

$\displaystyle\sum_{l=1}^{L}\frac{|E_{l}|}{\sqrt{\tau_{l}-1}}$
$\displaystyle=\sum_{l=1}^{L}\frac{f(l)}{\sqrt{F(l)-1}}=\int_{1}^{L}\frac{f(\lceil
x\rceil)}{\sqrt{F(\lceil x\rceil)-1}}\,dx$
$\displaystyle\leq\int_{1}^{L}\frac{f(x)}{\sqrt{F(x)-1}}\,dx=2(\sqrt{F(L)-1})$
$\displaystyle=2(\sqrt{\tau_{L}-1})\leq 2\sqrt{T}.$

∎

We introduce the following notation: for
$f:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$, let
$f^{\pi}(x):=\sum_{a}f(x,a)\pi(x,a)$. For all $t>0$, let $l_{t}$ denote the
episode number at time $t$. The following useful lemma is based on a
martingale argument.

######  Lemma 5.

Let $f:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$. Let
$\delta^{\prime}>0$. We have:

$\displaystyle\mathbb{P}\left[{\sum_{t=1}^{T}(\langle
f^{\pi_{l_{t}}},p\rangle-f(x_{t},a_{t}))\leq\sqrt{2T\log(1/\delta^{\prime})}}\right]\geq
1-\delta^{\prime}$ $\displaystyle\mathbb{P}\left[{\sum_{t=1}^{T}\big{|}\langle
f^{\pi_{l_{t}}},p\rangle-f(x_{t},a_{t})\big{|}\leq\sqrt{2T\log(2/\delta^{\prime})}}\right]\geq
1-\delta^{\prime}.$

###### Proof.

We define the filtration $\mathcal{F}_{t}=\sigma(x_{1},a_{1},...,x_{t},a_{t})$
and we first show that the sequence defined by $M_{t}=\langle
f^{\pi_{l_{t}}},p\rangle-f(x_{t},a_{t})$ is a martingale difference sequence
w.r.t. $\mathcal{F}_{t}$. $\mathbb{E}\left[{M_{t}}\right]<\infty$ since the
rewards are bounded. Next, the proof that
$\mathbb{E}\left[{M_{t}|\mathcal{F}_{t-1}}\right]=0$ relies on the fact that
$l_{t}$, and in turn the stationary policy $\pi_{l_{t}}$, are
$\mathcal{F}_{t-1}-$measurable.

Therefore,

$\displaystyle\mathbb{E}\left[{\langle
f^{\pi_{l_{t}}},p\rangle\big{|}\mathcal{F}_{t-1}}\right]=\langle
f^{\pi_{l_{t}}},p\rangle.$

We also have:

$\displaystyle\mathbb{E}\left[{f(x_{t},a_{t})\big{|}\mathcal{F}_{t-1}}\right]$
$\displaystyle=\mathbb{E}\left[{\sum_{x,a}f(x,a)\mathds{1}_{\\!\\{(x_{t},a_{t})=(x,a)\\}}\bigg{|}\mathcal{F}_{t-1}}\right]$
$\displaystyle=\sum_{x,a}f(x,a)\pi_{l_{t}}(x,a)=\langle
f^{\pi_{l_{t}}},p\rangle.$

Subtracting the two expressions above, we get
$\mathbb{E}\left[{M_{t}|\mathcal{F}_{t-1}}\right]=0$. $(M_{t})_{t}$ is thus a
Martingale difference sequence, such that $-1\leq M_{t}\leq 1$. The result
follows from Azuma-Hoeffding’s inequality.

∎

We now prove Theorem 1.

###### Proof.

We define $\mathcal{E}=\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3}$
to be the “good event”, with:

$\displaystyle\mathcal{E}_{1}=\\{\forall l\geq 1,\tilde{p}_{l}\in B_{l}\\},$
$\displaystyle\mathcal{E}_{2}=\\{\sum_{t=1}^{T}(\langle
r^{\pi_{l_{t}}},p\rangle-r(x_{t},a_{t}))\leq\sqrt{2T\log(3/\delta)}\\},$
$\displaystyle\mathcal{E}_{3}=\left\\{\forall
i,j,\quad\sum_{t=1}^{T}\big{|}\langle{\xi_{j}^{i}}^{\pi_{l_{t}}},p\rangle-{\xi_{j}^{i}}(x_{t},a_{t})\big{|}\leq\sqrt{2T\log\big{(}\frac{6\tilde{d}}{\delta}\big{)}}\right\\}.$

By Lemma 3, we have

$\displaystyle\mathbb{P}\left[{\exists l\geq 1,\tilde{p}_{l}\in
B_{l}}\right]\geq 1-\frac{\delta}{3}.$ (8)

Combining (8) with Lemma 5 and using union bounds,
$\mathbb{P}\left[{\mathcal{E}}\right]\geq 1-\delta$. From now on, we assume
that the good event $\mathcal{E}$ holds true.

#### Performance regret

We start by upper bounding the performance regret $R(T)$. Let
$\Delta_{l}=\sum_{t\in E_{l}}(g^{*}-r(x_{t},a_{t}))$ be the regret of episode
$l$. Let $(\pi_{l},\tilde{p}_{l})$ be the solution of the optimistic CMDP (4)
at episode $l$. Since $(\pi^{*},p)$ is feasible for (4), then $g^{*}\leq
g^{\tilde{p}_{l},\pi_{l}}$. We also note that

$g^{\tilde{p}_{l},\pi_{l}}=\sum_{x,a}r(x,a)\tilde{p}_{l}(x)\pi_{l}(x,a)=\sum_{x}r^{\pi_{l}}(x)\tilde{p}_{l}(x).$

Therefore, we have:

$\displaystyle\Delta_{l}$ $\displaystyle\leq\sum_{t\in
E_{l}}(g^{\tilde{p}_{l},\pi_{l}}-r(x_{t},a_{t}))$ (9)
$\displaystyle=\sum_{t\in
E_{l}}(\sum_{x}r^{\pi_{l}}(x)\tilde{p}_{l}(x)-r(x_{t},a_{t}))$
$\displaystyle=\sum_{t\in E_{l}}\sum_{x}r^{\pi_{l}}(x)(\tilde{p}_{l}(x)-p(x))$
$\displaystyle\quad+\sum_{t\in
E_{l}}(\sum_{x}r^{\pi_{l}}(x)p(x)-r(x_{t},a_{t}))\,$

Using Hölder’s inequality and the fact that $\|r\|_{\infty}=1$, the first term
can be bounded by $|E_{l}|\|\tilde{p}_{l}-p\|_{1}$. By validity of the
confidence intervals under event $\mathcal{E}$:

$\displaystyle\|\tilde{p}_{l}-p\|_{1}\leq
2\beta_{l}\leq\frac{2\sqrt{2|\mathcal{X}|\log\big{(}6|\mathcal{X}|T(T-1)/\delta\big{)}}}{\sqrt{\tau_{l}-1}}$
(10)

Summing up over episodes $l=1,...,L$:

$\displaystyle R(T)$ $\displaystyle\leq
2\sqrt{2|\mathcal{X}|\log\big{(}\frac{6|\mathcal{X}|T(T-1)}{\delta}\big{)}}\sum_{l=1}^{L}\frac{|E_{l}|}{\sqrt{\tau_{l}-1}}$
(11)
$\displaystyle+\sum_{t=1}^{T}(\sum_{x}r^{\pi_{l_{t}}}(x)p(x)-r(x_{t},a_{t})).$

We bound the first sum using Lemma 4. The second term can be bounded as in
Lemma 5 because $\mathcal{E}_{2}$ holds true. This gives us the resulting
bound which holds under $\mathcal{E}$:

$\displaystyle R(T)$ $\displaystyle\leq
4\sqrt{|\mathcal{X}|\log\big{(}\frac{6|\mathcal{X}|T(T-1)}{\delta}\big{)}T}+\sqrt{2T\log\big{(}\frac{3}{\delta}\big{)}}.$

#### Cost of constraint violations

The proof for the cost of constraint violations is very similar. Let us bound
$R_{j}^{i}(T):=\sum_{t=1}^{T}|\xi_{j}^{i}(x_{t},a_{t})|$ for all $i,j$. We
briefly drop the sub/superscripts $i,j$.

At each episode $l$, since $(\pi_{l},\tilde{p}_{l})$ is a solution of (4), we
have $h^{\tilde{p}_{l},\pi_{l}}=0$, and thus
$\sum_{x,a}\xi(x,a)\pi_{l}(x,a)\tilde{p}_{l}(x)=\sum_{x}\xi^{\pi_{l}}(x)\tilde{p}_{l}(x)=0$.
Therefore, we have:

$\displaystyle\left|\sum_{t=1}^{T}\xi(x_{t},a_{t})\right|$
$\displaystyle=\left|\sum_{l=1}^{L}\big{(}\sum_{t\in
E_{l}}\xi(x_{t},a_{t})-\sum_{x}\xi^{\pi_{l}}(x)\tilde{p}_{l}(x)\big{)}\right|$
$\displaystyle\leq\bigg{|}\sum_{l=1}^{L}\sum_{t\in
E_{l}}\sum_{x}\xi^{\pi_{l}}(x)(p(x)-\tilde{p}_{l}(x))$
$\displaystyle\quad\quad+\sum_{l=1}^{L}\big{(}\sum_{t\in
E_{l}}\xi(x_{t},a_{t})-\sum_{x}\xi^{\pi_{l}}(x)p(x)\big{)}\bigg{|}$
$\displaystyle\leq\sum_{l=1}^{L}\sum_{t\in
E_{l}}\left|\sum_{x}\xi^{\pi_{l}}(x)(p(x)-\tilde{p}_{l}(x))\right|$
$\displaystyle\quad\quad+\left|\sum_{l=1}^{L}\big{(}\sum_{t\in
E_{l}}\xi(x_{t},a_{t})-\sum_{x}\xi^{\pi_{l}}(x)p(x)\big{)}\right|$
$\displaystyle\leq\sum_{l=1}^{L}|E_{l}|\|\xi^{\pi_{l}}\|_{\infty}\|p-\tilde{p}_{l}\|_{1}$
$\displaystyle\quad\quad+\left|\sum_{t=1}^{T}\bigg{(}\xi(x_{t},a_{t})-\sum_{x}\xi^{\pi_{l_{t}}}(x)p(x)\bigg{)}\right|,$

where the first part of the last inequality is again by Hölder’s inequality.
Similarly to the performance regret, the first term is bounded using the
validity of confidence intervals under the good event $\mathcal{E}$ and Lemma
4, and the second term is bounded by the martingale argument using Lemma 5.
Hence, under $\mathcal{E}$ we have for any $i,j$:

$\displaystyle R_{j}^{i}(T)$ $\displaystyle\leq
4\sqrt{|\mathcal{X}|\log\big{(}\frac{6|\mathcal{X}|T(T-1)}{\delta}\big{)}T}+\sqrt{2T\log\big{(}\frac{6\tilde{d}}{\delta}\big{)}}.$

And thus the same bounds holds for $R^{c}(T)=\max_{i,j}R_{j}^{i}(T)$.

#### Representation loss

We may now derive the bound on representation loss.

Let $f(T)=O\big{(}\sqrt{|\mathcal{X}|\log(|\mathcal{X}|T/\delta)}\big{)}$. The
regret bounds imply that with $1-\delta$:

$\displaystyle R(T)=$ $\displaystyle g^{*}T-N(T)\leq f(T)\Rightarrow N(T)\geq
g^{*}T-f(T)$ $\displaystyle\frac{R^{c}(T)}{N(T)}=$
$\displaystyle\max_{i,j}\left|\frac{N_{j}^{i}(T)}{N(T)}-\rho_{j}^{i}\frac{N(T)}{N(T)}\right|\leq\frac{f(T)}{N(T)}$
i.e., $\displaystyle\|\lambda(C_{T})-\rho\|_{\infty}\leq\frac{f(T)}{N(T)}.$

Therefore, using $N(T)\geq 1$, we have:

$\displaystyle\|\lambda(C_{T})-\rho\|_{\infty}$
$\displaystyle\leq\frac{f(T)}{\max(1,g^{*}T-f(T))}$
$\displaystyle=O\bigg{(}\sqrt{\frac{|\mathcal{X}|\log(|\mathcal{X}|T/\delta)}{{g^{*}}^{2}T}}\bigg{)}.$

∎

##  Appendix C Alternative to RL-CMDP with Bernstein bounds

We present RL-CMDP-B, an alternative to RL-CMDP which uses Bernstein empirical
bounds Maurer and Pontil [2009].

At each episode $l$, the algorithm estimates the distributions by
$\hat{p}_{l}(x)=\frac{n_{\tau_{l}-1}(x)}{\tau_{l}-1}$ and maintains confidence
intervals $[\underline{p}_{l}(x),\overline{p}_{l}(x)]$. These are built using
Bernstein’s empirical inequality Maurer and Pontil [2009], which implies that
there exists constants $B_{1},B_{2}$ such that with probability $\geq
1-\frac{\delta}{3}$, for each $l\geq 1$ and $x\in\mathcal{X}$,

$\displaystyle|p(x)-\hat{p}_{l}(x)|\leq
B_{1}\sqrt{\frac{\hat{\sigma}_{l}^{2}(x)\log(\frac{6|\mathcal{X}|\tau_{l}}{\delta})}{1\land(\tau_{l}-1)}}+B_{2}\frac{\log(\frac{6|\mathcal{X}|\tau_{l}}{\delta})}{1\land(\tau_{l}-1)},$
(12)

where $\hat{\sigma}_{l}(x)=\sqrt{\hat{p}_{l}(x)(1-\hat{p}_{l}(x))}$.

Following e.g. Efroni et al. [2020], we re-write (4) as an extended LP by
introducing the state-action occupation measure $\mu(x,a)=\pi(x,a)p(x)$.

$\displaystyle\max_{\mu\in\mathbb{R}^{\mathcal{X}\times\mathcal{A}}}$
$\displaystyle\sum_{x,a}\mu(x,a)r(x,a)$ (13) u.c. $\displaystyle\mu\geq
0,\sum_{x,a}\mu(x,a)=1$ $\displaystyle\forall
x,\sum_{a}\mu(x,a)\leq\overline{p}_{l}(x)$ $\displaystyle\forall
x,\sum_{a}\mu(x,a)\geq\underline{p}_{l}(x)$ $\displaystyle\forall
i,j,\sum_{x,a}\mu(x,a)\xi_{j}^{i}(x,a)=0.$

The second to fourth constraints enforce the compatibility of $\mu$ with the
confidence intervals. Controlling each entry of $p$ with Bernstein bounds
instead of the $\ell^{1}$-norm allows for a simpler optimization problem than
the extended LP (5). We get the following regret bound:

######  Theorem 2 (Regret guarantees).

With probability $\geq 1-\delta$, the regret of RL-CMDP-B satisfies:

$\displaystyle
R(T)=O\big{(}\sqrt{|\mathcal{X}|T\log(|\mathcal{X}|T/\delta)}+|\mathcal{X}|\log(|\mathcal{X}|T/\delta)^{2}\big{)}$
$\displaystyle
R^{c}(T)=O\big{(}\sqrt{|\mathcal{X}|T\log(|\mathcal{X}|T/\delta)}+|\mathcal{X}|\log(|\mathcal{X}|T/\delta)^{2}\big{)}.$

With probability $\geq 1-\delta$, the representation loss satisfies:

$\displaystyle\|\lambda(C_{T})-\rho\|_{\infty}$
$\displaystyle=O\left(\frac{1}{g^{*}}\sqrt{\frac{|\mathcal{X}|\log\big{(}|\mathcal{X}|T/\delta\big{)}}{T}}+\frac{|\mathcal{X}|\log(|\mathcal{X}|T/\delta)^{2}}{g^{*}T}\right).$

When using Bernstein bounds, the representation loss carries
$O(|\mathcal{X}|\log(|\mathcal{X}|T/\delta)^{2})$. This factor but has a
bigger scaling with $|\mathcal{X}|$, but decreases rapidly in
$\frac{\log(T)^{2}}{T}$.

The Bernstein version of RL-CMDP may be advantageous for some candidate
distributions $p$. For example, if the support $\mathcal{S}$ of $p$ is very
small compared to $\mathcal{X}$, the first term in the Bernstein empirical
inequality (12) is equal to zero for all $x$ outside the support. Therefore,
the representation loss scales as:

$\displaystyle\|\lambda(C_{T})-\rho\|_{\infty}$
$\displaystyle=O\left(\frac{1}{g^{*}}\sqrt{\frac{|\mathcal{S}|\log\big{(}|\mathcal{S}|T/\delta\big{)}}{T}}+\frac{|\mathcal{X}|\log(|\mathcal{X}|T/\delta)^{2}}{g^{*}T}\right),$

where $|\mathcal{S}|\ll|\mathcal{X}|$. Thus, the second term with fast
decrease in $\frac{\log(T)^{2}}{T}$ controls the bound on representation loss.

###  C.1 Proofs

The following lemma states a useful inequality akin to Lemma 4.

######  Lemma 6.

We have:

$\displaystyle\sum_{l=1}^{L}\frac{|E_{l}|}{\tau_{l}-1}\leq\log(T)$

###### Proof.

The proof is similar to Lem. 13 in Zanette and Brunskill [2019]. Using the
same notation as in the proof of Lemma 4,

$\displaystyle\sum_{l=1}^{L}\frac{|E_{l}|}{\tau_{l}-1}$
$\displaystyle=\sum_{l=1}^{L}\frac{f(l)}{F(l)-1}=\int_{1}^{L}\frac{f(\lceil
x\rceil)}{F(\lceil x\rceil)-1}\,dx$
$\displaystyle\leq\int_{1}^{L}\frac{f(x)}{F(x)-1}\,dx=\log(F(L)-1)$
$\displaystyle=\log(\tau_{L}-1)\leq\log{T}.$

∎

We now prove Theorem 2.

###### Proof.

We re-use the same steps and notation as for the proof of Theorem 1.

Here instead, $\mathcal{E}_{1}$ is the event such that the confidence
intervals are valid (12). Under the high-probability good event
$\mathcal{E}=\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3}$, we thus
have:

$|\pi_{l}(x)-p(x)|\lesssim\sqrt{\frac{\hat{p}_{l}(x)(1-\hat{p}_{l}(x))b_{\delta,T}}{\tau_{l}-1}}+\frac{b_{\delta,T}}{\tau_{l}-1}$

where $b_{\delta,T}=\log(\frac{6|\mathcal{X}|T}{\delta})$.

In the following, the first inequality is by validity of the Bernstein
confidence intervals under $\mathcal{E}$, and the second inequality is by
Cauchy-Schwarz’s inequality:

$\displaystyle\sum_{t\in E_{l}}\sum_{x}r^{\pi_{l}}(x)(\tilde{p}_{l}(x)-p(x))$
(14) $\displaystyle\leq\sum_{t\in
E_{l}}\sum_{x}r^{\pi_{l}}(x)\sqrt{\frac{\hat{p}_{l}(x)(1-\hat{p}_{l}(x))b_{\delta,T}}{\tau_{l}-1}}$
$\displaystyle\quad+\sum_{t\in
E_{l}}\frac{b_{\delta,T}}{\tau_{l}-1}\underbrace{\sum_{x}r^{\pi_{l}}(x)}_{\leq|\mathcal{X}|}$
$\displaystyle\leq\sum_{t\in
E_{l}}\sqrt{\underbrace{(\sum_{x}1-\hat{p}_{l}(x))}_{\leq|\mathcal{X}|}\underbrace{(\sum_{x}\hat{p}_{l}(x)r^{\pi_{l}}(x)b_{\delta,T})}_{\leq
b_{\delta,T}}}\sqrt{\frac{1}{\tau_{l}-1}}$ $\displaystyle\quad+\sum_{t\in
E_{l}}\frac{|\mathcal{X}|b_{\delta,T}}{\tau_{l}-1}$

By Lemmas 4 and 6, we have:

$\displaystyle\sqrt{|\mathcal{X}|b_{\delta,T}}\sum_{l=1}^{L}\frac{|E_{l}|}{\sqrt{\tau_{l}-1}}\leq
2\sqrt{|\mathcal{X}|b_{\delta,T}T}$
$\displaystyle|\mathcal{X}|b_{\delta,T}\sum_{l=1}^{L}\frac{|E_{l}|}{\tau_{l}-1}\leq|\mathcal{X}|b_{\delta,T}\log(T).$

Summing up over episodes in inequality (14) and plugging in the above
inequalities gives the desired bound by following the steps of the proof of
Theorem 1. ∎

##  Appendix D Experiments

###  D.1 Details on the Brexit experiments

We provide in Table 2 the target vectors $(\rho_{j}^{i})_{i,j}$ and marginal
distributions $(\mathbb{P}^{p}[x^{i}=j])_{i,j}$ extracted from the Citizens’
Assembly on Brexit report Renwick et al. [2017].555
https://citizensassembly.co.uk/wp-content/uploads/2017/12/Citizens-Assembly-
on-Brexit-Report.pdf, pages 28-32. The report includes the volunteering rates
for each feature group, i.e. $\Pr[\text{volunteer}|x^{i}=j]$. To compute the
marginal distributions $(\Pr[x^{i}=j|\text{volunteer}])_{i,j}$, we thus use
Bayes’ rule to compute the probability of each feature group among the
volunteer population666In doing so, we notice that the probability of finding
non-voter volunteers is almost zero, hence we only consider “remain” and
“leave” for the feature Brexit vote. Indeed, the report states “The only
target that proved impossible to meet was that for non-voters in the 2016
referendum.” p.28., that is:

$\displaystyle\mathbb{P}^{p}[x^{i}=j]$
$\displaystyle=\Pr[x^{i}=j|\text{volunteer}]$
$\displaystyle=\frac{\Pr[\text{volunteer}|x^{i}=j]\Pr[x^{i}=j]}{\Pr[\text{volunteer}]}.$

We often have $\rho_{j}^{i}\neq\mathbb{P}^{p}[x^{i}=j]$. For example, compared
to the age target, we are less likely to find younger people ($\leq 34$ years
old) among volunteers. For gender, while the target was gender parity, we are
much less likely to find women than men in the volunteer population.

| Targets | Marginals
---|---|---
Ethnicity | 0.860 / 0.140 | 0.863 / 0.136
Social class | 0.550 / 0.450 | 0.556 / 0.444
Age | 0.288 / 0.344 / 0.367 | 0.154 / 0.432 / 0.414
Region |  | 0.233 / 0.160 / 0.093
---
/ 0.134 / 0.222 / 0.047
/ 0.082 / 0.028
| 0.179 / 0.155 / 0.090
---
/ 0.117 / 0.211 / 0.073
/ 0.154 / 0.021
Gender | 0.507 / 0.493 | 0.384 / 0.616
Brexit vote | 0.481 / 0.519 | 0.565 / 0.434
Table 2: Target quotas (from the report) and marginal distribution (computed
using Bayes’ rule) for the Brexit experiment.

For our experiments presented in Section 6, we used Python and the CPLEX LP
solver, and a machine with Intel Xeon Gold 6230 CPUs, 2.10 GHz, 1.3 MiB of
cache.

###  D.2 Experiments with dependent features

The goal of these experiments is to answer the following: what is the impact
of the dependence structure of the joint feature distribution $p$ on the
sample complexity and representation loss of our algorithms? Since we may only
retrieve marginal distributions from the Citizen’s Assembly on Brexit report,
we keep the target quotas on each feature but simulate joint feature
distributions from another dataset with demographic attributes, the standard
Adult Census Income dataset Dua and Graff [2017].

The Adult dataset consists of approximately $49.000$ entries of subjects in
the US, each with 14 demographic features and a binary label indicating
whether a subject’s income is above or below $50$K USD. We only keep features
that can be mapped to our Brexit Citizen’s Assembly example: gender, age,
ethnicity and income, which we use in lieu of social class. We do not consider
proportional representation for region and Brexit vote since there are no such
features in the Adult dataset. In our preprocessing of the Adult dataset, we
create the same three age categories ($<$35, 35-54, $>$54), the same two
ethnicity groups (white / non-white) and we use the binary income variable as
a proxy for social class, by assigning $>50$K to upper class and $\leq 50$K to
lower class. This leaves us with $4$ features with $2,2,2,3$ possible values.

To create dependencies between features, we consider two graphical structures
shown in Figure 3, and for each we fit a Bayesian network to the dataset to
generate a model of the joint distribution $p(x)$. We consider one structure
with little dependence, and one structure with strong dependence between
features.

(a) Structure 1: weak dependence.

(b) Structure 2: strong dependence.

Figure 3: Bayesian network structures for the Census Income dataset.  Figure
4: Effect of committee size $K$ on sample complexity and representation loss
for CMDP (known $p$) and RL-CMDP (unknown $p$), on the two different Bayesian
networks (1) and (2) fitted on the Census Income dataset.

Figure 4 shows that both when $p$ is known, the sample complexity is higher
when there is more dependence (Bayesian network (2)) between features, but the
representation loss is the same. When $p$ is unknown, the representation loss
is lower for structure (2) with more dependence, than structure (1) with
little dependence, but the sample size is higher for (2). For structure (2),
the representation loss is low ($\approx 0.07$) for $K=1000$. Importantly, it
implies that in practice, the representation loss is much lower than the worst
case bound given by Theorem 1.

##  Appendix E Detailed example for Section 4

We take the same attributes and same distribution as in Table 1, with
$\epsilon^{\prime}=\nicefrac{{1}}{{6}}$:

gender \ age | S | J
---|---|---
M | $\nicefrac{{1}}{{3}}$ | $\nicefrac{{1}}{{4}}$
F | $\nicefrac{{1}}{{4}}$ | $\nicefrac{{1}}{{6}}$

The target vectors are
$\rho^{\text{gender}}=(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$ and
$\rho^{\text{age}}=(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$, that is, an
ideal committee contains as many women as men and as many senior than junior.

We solve the linear program

$\displaystyle\max$
$\displaystyle\frac{\pi(MS,1)}{3}+\frac{\pi(FS,1)}{4}+\frac{\mu(MJ,1)}{4}+\frac{\mu(FJ,1)}{6}$
(15) u.c.
$\displaystyle\frac{\pi(MS,1)}{3}+\frac{\pi(FS,1)}{4}=\frac{\mu(MJ,1)}{4}+\frac{\mu(FJ,1)}{6}$
$\displaystyle\frac{\pi(MS,1)}{3}+\frac{\mu(MJ,1)}{4}=\frac{\pi(FS,1)}{4}+\frac{\mu(FJ,1)}{6}$

Its solution is

$\displaystyle\pi^{*}(MS,1)=\nicefrac{{1}}{{2}}$ (16)
$\displaystyle\pi^{*}(FJ,1)=1$ $\displaystyle\pi^{*}(MJ,1)=1$
$\displaystyle\pi^{*}(FS,1)=1$

Thus, each time the current volunteer is a senior male, we select him with
probability $\nicefrac{{1}}{{2}}$; all other volunteers are selected with
probability 1. The expected final composition of the pool is 30% of junior
male, 30% of senior female, 20% of junior female and 20% of senior male. As
the policy selects in average $\nicefrac{{5}}{{6}}$ of the volunteers, the
expected time until we select $K$ candidates is
$\mathbb{E}^{p,\pi^{*}}[\tau]=(\nicefrac{{6}}{{5}})K$.


# Pooling Strategies for Simplicial Convolutional Networks

###### Abstract

The goal of this paper is to introduce pooling strategies for simplicial
convolutional neural networks. Inspired by graph pooling methods, we introduce
a general formulation for a simplicial pooling layer that performs: i) local
aggregation of simplicial signals; ii) principled selection of sampling sets;
iii) downsampling and simplicial topology adaptation. The general layer is
then customized to design four different pooling strategies (i.e., max,
top-$k$, self-attention, and separated top-$k$) grounded in the theory of
topological signal processing. Also, we leverage the proposed layers in a
hierarchical architecture that reduce complexity while representing data at
different resolutions. Numerical results on real data benchmarks (i.e., flow
and graph classification) illustrate the advantage of the proposed methods
with respect to the state of the art.

Index Terms—  Topological signal processing, topological deep learning,
simplicial neural networks, pooling.

##  1 Introduction

In the last years, Graph Neural Networks (GNNs) [1, 2, 3] have shown
remarkable results in learning tasks involving data defined on irregular
domains (e.g., graphs), such as social networks, recommender systems,
cybersecurity, natural language processing, genomics, and many more [4, 3].
However, GNNs are designed to work with graphs, which consider only pairwise
relationships between data. On the contrary, many real-world phenomena involve
multi-way relationships as, e.g., in biological or social networks. Some
recent works in topological signal processing [5, 6] have shown that multi-way
relationships can be described using simplicial complexes, which are specific
instances of hyper-graphs with powerful algebraic representation able to model
higher-order interactions among nodes. Consequently, there was also a raising
interest in the development of (deep) neural network architectures able to
handle data defined on topological spaces, as summarized in the sequel.

Related works. Despite its recent birth, many contributions have been made to
the field of simplicial deep learning. In [7], the authors introduced a basic
simplicial neural network (SNN) architecture that performs convolution
exploiting high-order Laplacians without independently exploiting upper and
lower neighbourhoods. In [8], message passing neural networks (MPNNs) are
adapted to simplicial complexes, with the aggregation and updating functions
taking into account data defined on adjacent simplices, enabling message
exchange even among signals of different orders. The work in [9] exploits the
simplicial filters introduced in [10] to design a flexible and low-complexity
simplicial convolutional networks (SCNs) with spectral interpretability.
Finally, in [11, 12], simplicial attentional architectures are introduced.

Motivated by the fact that, both in convolutional neural networks (CNNs) and
in GNNs, the introduction of pooling layers was proved to be useful for
reducing the number of model parameters while improving the learning
performance, in this work we aim to endow SCNs with pooling strategies.
However, while for CNNs the pooling operation relies on aggregation based on
the natural local neighbourhood provided by the regular grid domain, even on
simpler graph domains the definition of local patches is not straightforward.
Early works tried to overcome this issue by using graph clustering algorithms
such as GraClus [13] or spectral methods [14] to produce a node assignment
that generalizes the notion of locality present in regular domains. The most
recent trends are instead focused on differentiable learnable operators that
can learn a node assignment [15], or simply keep some nodes while discarding
the others [16, 17]. Other works [18] discuss the class of _global pooling_
methods that reduce the graph to a single vector, ignoring topological
information. To the best of our knowledge, no previous works tackled the
problem of pooling for SCNs.

Contribution. The goal of this work is to introduce pooling strategies for
SCNs. Taking inspiration from the select-reduce-connect (SRC) paradigm [19],
we introduce a general simplicial pooling layer that comprises three steps: i)
a local aggregation step responsible for providing a meaningful summary of the
input signals; ii) a selection step responsible for selecting a proper subset
of simplices; finally, iii) a reduction step that downsamples the input
complex and the aggregated signals of step i) based on the simplices selected
in step ii). By tailoring steps ii) and iii), we introduce four different
simplicial pooling layers that generalize the well-known graph pooling
strategies. Also, we exploit the proposed simplicial pooling layers in a
jumping knowledge (JK) hierarchical architecture [20], which aggregates the
intermediate embeddings produced by the simplicial pooling layers to produce
the final output. Finally, we assess the performance of the proposed methods
on real-world graph and trajectory classification tasks, showing favorable
comparisons with respect to other techniques in terms of performance and
robustness to compression.

##  2 Background

Simplicial complex and signals. Given a finite set of vertices $\cal{V}$, a
$k$-simplex $\mathcal{H}_{k}$ is a subset of $\cal{V}$ with cardinality $k+1$.
A face of $\mathcal{H}_{k}$ is a subset with cardinality $k$ and thus a
$k$-simplex has $k+1$ faces. A coface of $\mathcal{H}_{k}$ is a
$(k+1)$-simplex that includes $\mathcal{H}_{k}$ [5, 21]. The lower
neighbourhood $\mathcal{N}_{\downarrow}$ of $\mathcal{H}_{k}$ is the set of
simplices with which it shares a face. Similarly, the upper neighbourhood
$\mathcal{N}_{\uparrow}$ of $\mathcal{H}_{k}$ is the set of simplices with
which it shares a co-face. A simplicial complex $\mathcal{X}_{K}$ of order $K$
is a collection of $k$-simplices $\mathcal{H}_{k}$, $k=0,\dots,K$ such that,
for any $\mathcal{H}_{k}\in\mathcal{X}_{K}$ then
$\mathcal{H}_{k-1}\in\mathcal{X}_{K}$ if
$\mathcal{H}_{k-1}\subset\mathcal{H}_{k}$. We denote the set of $k$-simplex in
$\mathcal{X}_{k}$ as
$\mathcal{D}_{k}:=\\{\mathcal{H}_{k}:\mathcal{H}_{k}\in\mathcal{X}_{K}\\}$,
with $|\mathcal{D}_{k}|=N_{k}$ and $\mathcal{D}_{k}\subset\mathcal{X}_{K}$.

A $k$-simplicial signal is defined as a mapping from the set of all
$k$-simplices contained in the complex to the real numbers:

$\mathbf{z}_{k}:\mathcal{D}_{k}\rightarrow\mathbb{R},\qquad k=0,1,\dots,K.$
(1)

In this paper, w.l.o.g., we will focus on complexes $\mathcal{X}_{2}$ of order
up to two, thus with a set of vertices $\mathcal{D}_{0}=\cal V$ with
$|\mathcal{V}|=V$, a set of edges $\mathcal{D}_{1}=\cal E$ with
$|\mathcal{E}|=E$ and a set of triangles $\mathcal{D}_{2}=\cal T$ with
$|\mathcal{T}|=T$. Given a simplex $\mathcal{H}_{k-1}\subset\mathcal{H}_{k}$,
we write $\mathcal{H}_{k-1}\sim\mathcal{H}_{k}$ to indicate that the
orientation of $\mathcal{H}_{k-1}$ is coherent with the one of
$\mathcal{H}_{k}$, whereas $\mathcal{H}_{k-1}\not\sim\mathcal{H}_{k}$ if it is
not.

Algebraic representations. The structure of a simplicial complex
$\mathcal{X}_{K}$ is described by the set of its incidence matrices
$\mathbf{B}_{k}$, with $k=1,\dots,K$. The $\mathbf{B}_{k}$’s describe which
$k$-simplices are incident to which $(k-1)$-simplices:

$[\mathbf{B}_{k}]_{i,j}=\begin{cases}0&\mathcal{H}_{k-1,i}\not\subset\mathcal{H}_{k,j};\\\
1&\mathcal{H}_{k-1,i}\subset\mathcal{H}_{k,j}\text{ and
}\mathcal{H}_{k-1,i}\sim\mathcal{H}_{k,j};\\\
-1&\mathcal{H}_{k-1,i}\subset\mathcal{H}_{k,j}\text{ and
}\mathcal{H}_{k-1,i}\not\sim\mathcal{H}_{k,j}.\end{cases}$ (2)

From the incidence information, we can build the high order combinatorial
Laplacian matrices [22] of order $k=0,\dots,K$:

$\displaystyle\mathbf{L}_{0}=\mathbf{B}_{1}\mathbf{B}_{1}^{T}$
$\displaystyle\mathbf{L}_{k}=\mathbf{B}_{k}^{T}\mathbf{B}_{k}+\mathbf{B}_{k+1}\mathbf{B}_{k+1}^{T}=\mathbf{L}_{k,d}+\mathbf{L}_{k,u}$
(3) $\displaystyle\mathbf{L}_{k}=\mathbf{B}_{K}^{T}\mathbf{B}_{K}.$

The term $\mathbf{L}_{k,d}$ in (3), also known as lower Laplacian, encodes the
lower adjacency of $k$-order simplices; the second term $\mathbf{L}_{k,u}$,
also known as upper Laplacian, encodes the upper adjacency of $k$-order
simplices. Thus, for example, two edges are lower adjacent if they share a
common vertex, whereas they are upper adjacent if they are faces of a common
triangle. Note that the vertices of a graph can only be upper adjacent if they
are incident to the same edge. This is why $\mathbf{L}_{0}$ contains only one
term, and it corresponds to the usual graph Laplacian.
Hodge Decomposition. High order Laplacians admit a Hodge decomposition [21],
such that any $k$-simplicial signal $\mathbf{z}_{k}\in\mathbb{R}^{N_{k}}$ can
be decomposed as:

$\mbox{$\mathbf{z}$}_{k}=\mathbf{B}_{k}^{T}\mbox{$\mathbf{z}$}_{k-1}+\mathbf{B}_{k+1}\mbox{$\mathbf{z}$}_{k+1}+\mbox{$\mathbf{z}$}_{k,h},$
(4)

for $k=0,1,\dots,K$. The first term
$\mathbf{B}_{k}^{T}\mbox{$\mathbf{z}$}_{k-1}$ of (4) is called irrotational
component, the second term $\mathbf{B}_{k+1}\mbox{$\mathbf{z}$}_{k+1}$
solenoidal component, and the third term $\mbox{$\mathbf{z}$}_{k,h}$ harmonic
component. In the sequel, we will focus w.l.o.g. on edge flow signals and
complexes of order 2. Therefore, we will drop the subscripts and denote
$\mathbf{z}_{1}$ with $\mathbf{z}$, $\mathbf{L}_{1}$ with $\mathbf{L}$,
$\mathbf{L}_{1,d}$ with $\mathbf{L}_{d}$, $\mathbf{L}_{1,u}$ with
$\mathbf{L}_{u}$ and $\mathcal{X}_{2}$ with $\mathcal{X}$. Moreover, we denote
the lower and upper neighborhoods of the $i$-th edge with
$\mathcal{N}_{i,\downarrow}$ and $\mathcal{N}_{i,\uparrow}$, respectively.

$\sum$PoolSCNPoolSCNreadoutreadoutMLP

Fig. 1: Example of simplicial pooling and JK hierarchical architecture.

##  3 Simplicial Convolutional Networks with Pooling Layers

The Hodge decomposition in (4) suggests to separately filter the components of
simplicial signals. Indeed, the work in [10] introduced linear shift-invariant
(LSI) filters for simplicial signals, which can be seen as a generalization of
LSI graph filters that exploit both upper and lower connectivities. A
simplicial convolutional neural network is made by the concatenation of
several layers composed by a point-wise non-linearity applied to a bank of LSI
simplicial filters plus a residual connection [9]. In this paper, we
generalize the layer structure of [9] introducing a a family of pooling
strategies encoded into the mapping $\mathcal{P}(\cdot)$. In particular,
letting $\mathbf{X}\in\mathbb{R}^{E\times G}$ be the matrix collecting $G$
edge signals on its columns, the layer of an SCN endowed with pooling
mechanisms (SCNP) can be written as:

$\displaystyle\mathbf{Y}=\sigma\Bigg{[}\mathcal{P}\Bigg{(}$
$\displaystyle\underbrace{\sum_{p=1}^{J_{d}}\mathbf{L}_{d}^{p}\mathbf{X}\mathbf{D}_{p}}_{\mathbf{Z}_{d}}+\underbrace{\sum_{p=1}^{J_{u}}\mathbf{L}_{u}^{p}\mathbf{X}\mathbf{U}_{p}}_{\mathbf{Z}_{u}}+\underbrace{\mathbf{X}\mathbf{H}}_{\mathbf{Z}_{h}}\Bigg{)}\Bigg{]},\vspace{-.1cm}$
(5)

where $\mathbf{Y}\in\mathbb{R}^{E^{\prime}\times F}$, with $E^{\prime}\leq E$;
the filters and residual weights
$\big{\\{}\mathbf{D}_{p}\big{\\}}_{p=1}^{J_{d}}$,
$\big{\\{}\mathbf{U}_{p}\big{\\}}_{p=1}^{J_{u}}$ and $\mathbf{H}$
$\in\mathbb{R}^{G\times F}$ are learnable parameters, while the order $J_{d}$
and $J_{u}$ of the filters, the number $F$ of output signals, and the non-
linearity $\sigma(\cdot)$ are hyperparameters to be chosen at each layer.
Therefore, an SCNP of depth $L$ is built as the stack of $L$ layers defined as
in (5); the SCN layer in [9] is recovered from (5) removing the pooling stage.

###  3.1 Design of simplicial pooling mapping

In this paragraph, we present a general formulation for a simplicial pooling
mapping, which will then be tailored to design four different pooling
strategies. Let us first denote the input to the pooling mapping in (5) as
$\mathbf{Z}=\mathbf{Z}_{d}+\mathbf{Z}_{u}+\mathbf{Z}_{h}\in\mathbb{R}^{E\times
F}$, and let the simplicial complex structure be encoded into
$\mathcal{X}=(\mathbf{L}_{u},\mathbf{L}_{d})$. We also denote as
$\mathbf{Z}^{\prime}\in\mathbb{R}^{E^{\prime}\times F}$ the output of the
pooling layer in (5). Then, formally, we define a simplicial pooling layer as
the mapping

$\mathcal{P}:(\mathcal{X},\mathbf{Z})\mapsto(\mathcal{X}^{\prime},\mathbf{Z}^{\prime}),$
(6)

which takes as input a simplicial complex $\mathcal{X}$ and signals
$\mathbf{Z}\in\mathbb{R}^{E\times F}$ defined on it, and returns as output a
sub-complex $\mathcal{X}^{\prime}\subset\mathcal{X}$ and signals
$\mathbf{Z}^{\prime}\in\mathbb{R}^{E^{\prime}\times F}$ defined on it, with
$E^{\prime}<E$.

Following the pooling paradigm introduced in [19] for GNNs, we propose to
model the layer in (6) as the composition of three operations: a local
aggregation step, a selection step, and a reduction step. The local
aggregation step is responsible for providing summary signals
$\widetilde{\mathbf{Z}}\in\mathbb{R}^{E\times F}$ of the input signals
$\mathbf{Z}\in\mathbb{R}^{E\times F}$ leveraging the connectivity induced by
the complex $\mathcal{X}$. Formally, we define it as the local mapping:

$\textbf{(Aggregation)}\quad\mathcal{A}:(\mathcal{X},\mathbf{Z})\mapsto(\mathcal{X},\widetilde{\mathbf{Z}}).$
(7)

The mapping in (7) is local in the sense that the aggregated signals
$[\widetilde{\mathbf{Z}}]_{i}$ of the $i$-th edge are function only of the
signals of its (lower and/or upper) neighbours $[\widetilde{\mathbf{Z}}]_{j}$,
$j\in\mathcal{N}_{i,\downarrow}$ and/or $\mathcal{N}_{i,\uparrow}$.

The selection step is responsible for choosing a subset
$\mathcal{E}^{\prime}\subset\mathcal{E}$ of edges that will compose the
1-skeleton of the sub-complex $\mathcal{X}^{\prime}$. Formally, we define it
as a mapping:

$\textbf{(Selection)}\quad\mathcal{S}:(\mathcal{X},\widetilde{\mathbf{Z}})\mapsto\mathcal{E}^{\prime}.$
(8)

The cardinality of $\mathcal{E}^{\prime}$ is tuned via the pooling ratio
$r\in(0,1]$ (a hyperparameter to be chosen), such that
$|\mathcal{E}^{\prime}|=E^{\prime}=\lfloor r\cdot E\rfloor$.

Finally, the reduction step is responsible for properly downsampling the input
complex $\mathcal{X}$ and the aggregated signals $\widetilde{\mathbf{Z}}$ to
obtain the output sub-complex $\mathcal{X}^{\prime}$ and the output signals
$\mathbf{Z}^{\prime}\in\mathbb{R}^{E^{\prime}\times F}$, based on the edge set
$\mathcal{E}^{\prime}$ chosen through the selection set. Formally, we define
it as a mapping:

$\textbf{(Reduction)}\quad\mathcal{R}:(\mathcal{E}^{\prime},\mathcal{X},\widetilde{\mathbf{Z}})\mapsto(\mathcal{X}^{\prime},\mathbf{Z}^{\prime}).$
(9)

We assume that the reduction mapping in (9) is given by the concurrent
application of two independent operations, i.e.,
$\mathcal{R}=(\mathcal{R}_{S},\mathcal{R}_{C})$, which separately downsample
signal and simplicial complex structure, respectively, and are defined as:

(Signal reduction)
$\displaystyle\mathcal{R}_{S}:(\mathcal{E}^{\prime},\widetilde{\mathbf{Z}})\mapsto\mathbf{Z}^{\prime},$
(10) (Complex reduction)
$\displaystyle\mathcal{R}_{C}:(\mathcal{E}^{\prime},\mathcal{X})\mapsto\mathcal{X}^{\prime}.$
(11)

The operations (10)-(11) compute the signals $\mathbf{Z}^{\prime}$ and the
complex structure $\mathcal{X}^{\prime}$ at the output of the pooling layer,
respectively.

In summary, the general pooling mapping $\mathcal{P}$ in (6) is given by the
composition of the three operations in (7)-(9), i.e.,

$\mathcal{P}=\mathcal{R}\circ\mathcal{S}\circ\mathcal{A}.$ (12)

We assume that the aggregation in (7) is kept fixed (e.g., max or mean). Also,
the complex reduction in (11) is computed as follows: if an edge $e$ belongs
to $\mathcal{E}$ but it is not in $\mathcal{E}^{\prime}$, the lower
connectivity is updated by disconnecting the nodes that are on the boundary of
$e$, while the upper connectivity is updated by removing the triangles that
have $e$ on their boundaries.

###  3.2 Simplicial pooling strategies

In this paragraph, we customize the selection and signal reduction steps in
(8) and (10) to design four pooling strategies.

Max pooling: The first method is an extension of the Max Pooling strategy
commonly used in CNNs. It selects the subset of edges $\mathcal{E}^{\prime}$
by ranking the absolute values of the sum of the aggregated signals
$\widetilde{\mathbf{Z}}$ of each edge. Formally, we define:

$\displaystyle\mathcal{S}:\quad\mbox{$\mathbf{y}$}=\left|\widetilde{\mathbf{Z}}\,\mathbf{1}\right|,\quad\mathcal{E}^{\prime}=\textrm{top}_{E^{\prime}}(\mbox{$\mathbf{y}$}),$
(13)
$\displaystyle\mathcal{R}_{S}:\quad\mathbf{Z}^{\prime}=[\widetilde{\mathbf{Z}}]_{i\in\mathcal{E}^{\prime}},$
(14)

where $\mathbf{1}$ is the vector of all ones, and
$\textrm{top}_{E^{\prime}}(\cdot)$ selects the indexes of the the $E^{\prime}$
largest entries of its vector argument.

Top-$k$ pooling: The next layer is a generalization of those proposed in [16,
18] for GNNs. It selects the subset of edges $\mathcal{E}^{\prime}$ ranking a
learnable weighted combination of the aggregated signals
$\widetilde{\mathbf{Z}}$ of each edge. Then, it computes the reduced signals
as a scaled version of $\widetilde{\mathbf{Z}}$ with coefficients in $[0,1]$
given by a normalization of the aforementioned weighted combination. Formally,
we have:

$\displaystyle\mathcal{S}:\quad\mbox{$\mathbf{y}$}=\frac{\widetilde{\mathbf{Z}}\,\mbox{$\mathbf{p}$}}{\|\mbox{$\mathbf{p}$}\|_{2}},\quad\mathcal{E}^{\prime}=\textrm{top}_{E^{\prime}}(\mbox{$\mathbf{y}$})$
(15)
$\displaystyle\mathcal{R}_{S}:\quad\mathbf{Z}^{\prime}=[\widetilde{\mathbf{Z}}\odot\tanh(\mbox{$\mathbf{y}$}\mathbf{1}^{T})]_{i\in\mathcal{E}^{\prime}},\vspace{-.1cm}$
(16)

where $\mathbf{p}$ is a learnable vector, and $\odot$ is the Hadamard product.

| Method | Graph Classification | Edge Flow Classification
---|---|---|---
| DD | PROTEINS | MSRC21 | NCI109 | Ocean Drifters | Synthetic Flow
GCNs |  Top-$k$ | $78.82\pm 3.49$ | $73.75\pm 3.32$ | $85.61\pm 5.60$ | $74.35\pm 2.76$ | N/A | N/A
SelfAtt | $78.52\pm 1.88$ | $73.75\pm 3.32$ | $89.12\pm 10.33$ | $76.76\pm 2.21$ | N/A | N/A
SCNPs |  NoPool (SCNs [9]) | $78.57\pm 4.64$ | $75.00\pm 2.19$ | $92.98\pm 2.48$ | $76.28\pm 3.97$ | $98.25\pm 1.11$ | $100.0\pm 0.0$
Random | $84.37\pm 6.68$ | $74.29\pm 2.48$ | $93.33\pm 3.80$ | $74.47\pm 3.79$ | $76.25\pm 6.72$ | $98.82\pm 0.58$
Max | $\mathbf{88.07}\pm 3.86$ | $78.57\pm 2.09$ | $\mathbf{96.14}\pm 3.14$ | $72.92\pm 4.60$ | $100.0\pm 0.0$ | $100.0\pm 0.0$
Top-$k$ | $84.87\pm 3.61$ | $79.29\pm 2.31$ | $95.79\pm 2.94$ | $75.36\pm 6.95$ | $\mathbf{100.0}\pm 0.0$ | $100.0\pm 0.0$
SelfAtt | $86.39\pm 4.38$ | $\mathbf{79.46}\pm 4.14$ | $95.79\pm 2.94$ | $71.62\pm 6.38$ | $86.13\pm 5.89$ | $99.99\pm 0.04$
SepTop-$k$ | $83.36\pm 7.09$ | $74.64\pm 4.22$ | $\mathbf{96.14}\pm 0.78$ | $\mathbf{80.09}\pm 2.35$ | $99.62\pm 0.56$ | $\mathbf{100.0}\pm 0.0$

Table 1: Accuracy on graph and trajectory classification

Self-Attention Pooling: This method is a generalization of SagPool [17]. The
main difference with Top-$k$ is that the ranking is computed over the output
of a simplicial convolutional layer as in (5) without pooling and with one
output signal, here briefly denoted as scn. Formally, we have:

$\displaystyle\mathcal{S}:\quad\mbox{$\mathbf{y}$}=\textsc{scn}(\widetilde{\mathbf{Z}},\mathbf{L}_{d},\mathbf{L}_{u}),\quad\mathcal{E}^{\prime}=\textrm{top}_{E^{\prime}}(\mbox{$\mathbf{y}$}),$
(17)
$\displaystyle\mathcal{R}_{S}:\quad\mathbf{Z}^{\prime}=[\widetilde{\mathbf{Z}}\odot\tanh(\mbox{$\mathbf{y}$}\mathbf{1}^{T})]_{i\in\mathcal{E}^{\prime}}.$
(18)

Separated Top-$k$ pooling: The Hodge Decomposition in (4) and the consequent
structure of the SCNP layer in (5) suggest to design pooling layers based on
the computation of three different aggregated signals:
$\widetilde{\mathbf{Z}}_{d}$ (obtained from $\mathbf{Z}_{d}$),
$\widetilde{\mathbf{Z}}_{u}$ (obtained from $\mathbf{Z}_{u}$), and
$\widetilde{\mathbf{Z}}_{h}$ (obtained from $\mathbf{Z}_{h}$). Consequently,
we will have three corresponding score vectors $\mbox{$\mathbf{y}$}_{d}$,
$\mbox{$\mathbf{y}$}_{u}$, and $\mbox{$\mathbf{y}$}_{h}$, respectively. Thus,
the “separated” version of the Top$-k$ layer in (15)-(16) is given by:

$\displaystyle\mathcal{S}:\begin{dcases}\mbox{$\mathbf{y}$}_{d}=\frac{\widetilde{\mathbf{Z}}_{d}\,\mbox{$\mathbf{p}$}_{d}}{\|\mbox{$\mathbf{p}$}_{d}\|},\;\mbox{$\mathbf{y}$}_{u}=\frac{\widetilde{\mathbf{Z}}_{u}\,\mbox{$\mathbf{p}$}_{u}}{\|\mbox{$\mathbf{p}$}_{u}\|},\;\mbox{$\mathbf{y}$}_{h}=\frac{\widetilde{\mathbf{Z}}_{h}\,\mbox{$\mathbf{p}$}_{h}}{\|\mbox{$\mathbf{p}$}_{h}\|}\\\
\mathcal{E}^{\prime}=\textrm{top}_{E^{\prime}}(\mbox{$\mathbf{y}$}_{d}+\mbox{$\mathbf{y}$}_{u}+\mbox{$\mathbf{y}$}_{h})\end{dcases}$
(19)
$\displaystyle\mathcal{R}_{S}:\begin{dcases}&\mathbf{Z}^{\prime}_{d}=[\widetilde{\mathbf{Z}}_{d}\odot\tanh(\mbox{$\mathbf{y}$}_{d}\mathbf{1}^{T})]_{i\in\mathcal{E}^{\prime}}\\\
&\mathbf{Z}^{\prime}_{u}=[\widetilde{\mathbf{Z}}_{u}\odot\tanh(\mbox{$\mathbf{y}$}_{u}\mathbf{1}^{T})]_{i\in\mathcal{E}^{\prime}}\\\
&\mathbf{Z}^{\prime}_{h}=[\widetilde{\mathbf{Z}}_{h}\odot\tanh(\mbox{$\mathbf{y}$}_{h}\mathbf{1}^{T})]_{i\in\mathcal{E}^{\prime}}\\\
&\mathbf{Z}^{\prime}=\mathbf{Z}^{\prime}_{d}+\mathbf{Z}^{\prime}_{u}+\mathbf{Z}^{\prime}_{h}\end{dcases}$
(20)

where $\mbox{$\mathbf{p}$}_{u}$, $\mbox{$\mathbf{p}$}_{d}$, and
$\mbox{$\mathbf{p}$}_{h}$ are learnable vectors. Also all the previous methods
can be reformulated in this “separated” version, but we leave their
presentation and assessment for future works.

###  3.3 Hierarchical Architecture

In this paragraph, we introduce a JK hierarchical architecture aimed at
exploiting the different data representations obtained after each pooling
stage $l\in\\{1,...,L\\}$. A pictorial overview of the proposed JK
hierarchical architecture is shown in Fig. 1. In particular, applying a
readout operation, each intermediate compact representation obtained at the
output of layer $l$ collapses the current signals (and complex) into a single
embedding vector. For instance, a possible choice is concatenating the mean
and the maximum of the current signals. These vectors are then aggregated to
compose a global final embedding. For instance, if the same number of output
signals is used at each layer, the intermediate representations can be summed
to obtain a single global embedding vector. Finally, the global embedding can
be passed through a multi-layer perceptron (MLP), if it is needed for the
task. In the case of transductive (semisupervised) tasks, both the
intermediate and global embeddings might be unnecessary and can be neglected.

##  4 Numerical Experiments

In this section, we assess the performance of the proposed simplicial pooling
layers and hierarchical architecture on two learning tasks: trajectory
classification [8], and real-world graph [23] classification
111https://github.com/domenicocinque/spm. We compare the four proposed
simplicial pooling layers with a random pooling strategy, and with plain SCNs
having no pooling layers. Also, for graph classification, we show the results
obtained using GCNs [3] equipped with the “graph counterpart” of the proposed
simplicial pooling layers. All the hyper-parameters are tuned to obtain the
best performance per each dataset, except for the pooling ratio, which we keep
fixed at $r=0.7$. We compute the intermediate and global embeddings via mean-
maximum concatenation and sum, respectively. The models are trained for 150
epochs using the Adam optimizer [24] and early stopping with patience $25$.
All the experiments are averaged on five random seeds.

We first test the proposed simplicial pooling on two flow classification
tasks, namely the synthetic flow and ocean drifter datasets, whose details can
be found in [6, 8]. In Table 1 (right side), we compare the accuracy obtained
by all the considered methods, illustrating the gain introduced by the
proposed simplicial pooling layers for both datasets. Then, to assess the
accuracy-complexity tradeoff obtained by the proposed strategies, in Fig. 2 we
show the accuracy of the classification task versus the pooling ratio for the
synthetic flow dataset considering three pooling methods. As we can see from
Fig. 2, the accuracy mildly decreases with the pooling ratio, especially for
the Separated Top-$k$ strategy, illustrating the very good accuracy-complexity
trade-off obtained by the proposed methods.

Fig. 2: Accuracy versus pooling ratio.

Finally, we study the performance of the proposed simplicial pooling layers on
real-world graph classification tasks on the popular TUDataset [23]
collection. To obtain simplicial complexes from the graphs, we follow the
clique complex lifting procedure proposed in [8], while the input edge signals
are computed as the average of the graph signals of the boundary nodes. Then,
in Table 1 (left side), we can see how the proposed SCNPs outperform SCNs with
random pooling layers or no pooling, and the GCNs counterpart architectures.

##  5 Conclusions

In this paper, we have proposed a general formulation of a pooling layer for
simplicial convolutional neural networks, designed as the composition of a
local aggregation mapping, a selection mapping, and a reduction mapping. The
proposed methodology is then tailored to design four different simplicial
pooling layers, which generalize known graph pooling strategies for simplicial
neural architectures. Numerical results on real and synthetic benchmarks
illustrate the favorable performance of the proposed strategies with respect
to other methods available in the literature. Future extensions include more
complex simplicial architectures [8], or cell complex neural networks [25, 26,
27].

## References

  * [1] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst,  “Geometric deep learning: going beyond euclidean data,”  IEEE Signal Processing Magazine, vol. 34, no. 4, pp. 18–42, 2017\.
  * [2] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun,  “Spectral networks and locally connected networks on graphs,”  arXiv preprint arXiv:1312.6203, 2013.
  * [3] Thomas N Kipf and Max Welling,  “Semi-supervised classification with graph convolutional networks,”  arXiv preprint arXiv:1609.02907, 2016.
  * [4] D. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst,  “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,”  IEEE Signal Processing Magazine, vol. 30, 10 2012.
  * [5] Sergio Barbarossa and Stefania Sardellitti,  “Topological signal processing over simplicial complexes,”  IEEE Transactions on Signal Processing, vol. 68, pp. 2992–3007, 2020.
  * [6] Michael T Schaub, Austin R Benson, Paul Horn, Gabor Lippner, and Ali Jadbabaie,  “Random walks on simplicial complexes and the normalized hodge 1-laplacian,”  SIAM Review, vol. 62, no. 2, pp. 353–391, 2020.
  * [7] Stefania Ebli, Michaël Defferrard, and Gard Spreemann,  “Simplicial neural networks,”  in NeurIPS 2020 Workshop on Topological Data Analysis and Beyond, 2020.
  * [8] Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montufar, Pietro Liò, and Michael M Bronstein,  “Weisfeiler and lehman go topological: Message passing simplicial networks,”  in ICLR 2021 Workshop on Geometrical and Topological Representation Learning, 2021.
  * [9] Maosheng Yang, Elvin Isufi, and Geert Leus,  “Simplicial convolutional neural networks,”  in ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2022, pp. 8847–8851.
  * [10] Maosheng Yang, Elvin Isufi, Michael T. Schaub, and Geert Leus,  “Finite impulse response filters for simplicial complexes,”  in 2021 29th European Signal Processing Conference (EUSIPCO), 2021, pp. 2005–2009.
  * [11] L. Giusti, Claudio Battiloro, Paolo Di Lorenzo, Stefania Sardellitti, and Sergio Barbarossa,  “Simplicial attention neural networks,”  ArXiv, vol. abs/2203.07485, 2022.
  * [12] Christopher Wei Jin Goh, Cristian Bodnar, and Pietro Lio,  “Simplicial attention networks,”  in ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
  * [13] Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis,  “Weighted graph cuts without eigenvectors a multilevel approach,”  IEEE transactions on pattern analysis and machine intelligence, vol. 29, no. 11, pp. 1944–1957, 2007.
  * [14] Yao Ma, Suhang Wang, Charu C. Aggarwal, and Jiliang Tang,  “Graph convolutional networks with eigenpooling,”  Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
  * [15] Zhen Zhang, Jiajun Bu, Martin Ester, Jianfeng Zhang, Chengwei Yao, Zhi Yu, and Can Wang,  “Hierarchical graph pooling with structure learning,”  arXiv preprint arXiv:1911.05954, 2019.
  * [16] Hongyang Gao and Shuiwang Ji,  “Graph u-nets,”  IEEE transactions on pattern analysis and machine intelligence, vol. PP, 2019.
  * [17] Junhyun Lee, Inyeop Lee, and Jaewoo Kang,  “Self-attention graph pooling,”  in 36th International Conference on Machine Learning, ICML 2019. International Machine Learning Society (IMLS), 2019, pp. 6661–6670.
  * [18] Cătălina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, and Pietro Liò,  “Towards sparse hierarchical graph classifiers,”  arXiv preprint arXiv:1811.01287, 2018.
  * [19] Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi,  “Understanding pooling in graph neural networks,”  arXiv:2110.05292, 2021.
  * [20] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka,  “Representation learning on graphs with jumping knowledge networks,”  in International conference on machine learning. PMLR, 2018, pp. 5453–5462.
  * [21] Lek-Heng Lim,  “Hodge laplacians on graphs,”  Siam Review, vol. 62, no. 3, pp. 685–715, 2020.
  * [22] T.E. Goldberg,  “Combinatorial laplacians of simplicial complexes,”  Senior Thesis, Bard College, 2002.
  * [23] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann,  “Tudataset: A collection of benchmark datasets for learning with graphs,”  in ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
  * [24] Diederik P Kingma and Jimmy Ba,  “Adam: A method for stochastic optimization,”  in ICLR (Poster), 2015.
  * [25] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein,  “Weisfeiler and lehman go cellular: Cw networks,”  Advances in Neural Information Processing Systems, vol. 34, pp. 2625–2640, 2021.
  * [26] Mustafa Hajij, Kyle Istvan, and Ghada Zamzmi,  “Cell complex neural networks,”  arXiv preprint arXiv:2010.00743, 2020.
  * [27] Lorenzo Giusti, Claudio Battiloro, Lucia Testa, Paolo Di Lorenzo, Stefania Sardellitti, and Sergio Barbarossa,  “Cell attention networks,”  arXiv:2209.08179, 2022.