# Cascading Bandit under Differential Privacy

Kun Wang1, Jing Dong2, Baoxiang Wang3 Shuai Li1, Shuo Shao1
1Shanghai Jiao Tong University,
2University of Michigan,
3The Chinese University of Hong Kong, Shenzhen.
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper studies _differential privacy (DP)_ and _local differential privacy
(LDP)_ in cascading bandits. Under DP, we propose an algorithm which
guarantees $\epsilon$-indistinguishability and a regret of
$\mathcal{O}((\frac{\log T}{\epsilon})^{1+\xi})$ for an arbitrarily small
$\xi$. This is a significant improvement from the previous work of
$\mathcal{O}(\frac{\log^{3}T}{\epsilon})$ regret. Under
($\epsilon$,$\delta$)-LDP, we relax the $K^{2}$ dependence through the
tradeoff between privacy budget $\epsilon$ and error probability $\delta$, and
obtain a regret of $\mathcal{O}(\frac{K\log(1/\delta)\log T}{\epsilon^{2}})$,
where $K$ is the size of the arm subset. This result holds for both Gaussian
mechanism and Laplace mechanism by analyses on the composition. Our results
extend to combinatorial semi-bandit. We show respective lower bounds for DP
and LDP cascading bandits. Extensive experiments corroborate our theoretic
findings.

##  1 Introduction

There exists a rich literature on multi-armed bandits (MAB) as it captures a
most fundamental problem in sequential decision making - the exploration-
exploitation dilemma (Auer et al., 2002a, b; Bubeck and Cesa-Bianchi, 2012;
Besbes et al., 2014). Despite its simpleness, the MAB problem is found use in
many important applications such as online advertising and clinical trials. In
the original stochastic case of MAB, an agent is presented with $K$ arms and
is asked to pull an arm at each round through a finite-time horizon. Depending
on the agent’s choice, the agent will receive a reward and its goal is set to
maximizing the cumulative reward. The natural choice of performance metric is
thus the difference between the optimal reward possible and the actual reward
received by the agent, which is termed _regret_ in bandit literature.

The original stochastic case of the multi-armed bandits model, though
powerful, is insufficient to cope with the complexity of real applications.
The reward feedback is rarely as straightforward as depicted in stochastic
MAB. The cascading bandit problem is then proposed with the intention to
better model complicated situations common in applications such as
recommendation systems and search engines (Kveton et al., 2015a, b; Zong et
al., 2016; Li et al., 2016; Cheung et al., 2019; Wang et al., 2021). This
variant of MAB gives a realistic depiction of user behavior when searching for
attractive things. Cascading bandit is also a sequential learning process,
where in each round the agent recommends a list of arms to the user. The user
checks from the start of the list and stops at the first attractive item,
which is manifested by clicks in web recommendation. Then the agent receives
the feedback in the form of user’s click information.

While the cascading bandit model greatly assists the development of real
applications such as recommendation systems, it raises concern of privacy.
Many applications rely heavily on this sensitive user data which reveals the
preference of a particular user. If additional measures were not taken, one
can easily get this information by observing the difference of the algorithm’s
output (Dwork et al., 2006). For example, in a shopping website, users’ click
information and browsing history show the preference for some commodities, and
companies can use this information to conduct price discrimination. Since
first proposed in 2006, _differential privacy (DP)_ becomes a standard in
privacy notion because of its well-defined measure of privacy (Dwork et al.,
2006, 2010, 2014; Abadi et al., 2016). Modifying algorithms to make them
possess privacy guarantees is emergent nowadays. An algorithm is regarded to
own the capability of protecting differential privacy if the difference
between outputs of this algorithm over two adjacent inputs is insignificant,
as desired.

#### Technical difficulty:

First, the cascading bandits involve a non-linear reward function. Directly
injecting noise into the data may lead to much larger regret. Under the
canonical definition of differential privacy, bandits algorithms are known to
enjoy an upper bound of $\mathcal{O}(\log^{3}T)$ (Mishra and Thakurta, 2015;
Chen et al., 2020). Compare to the well known $\mathcal{O}(\log T)$ non
private upper bound (Auer et al., 2002a; Chen et al., 2013; Kveton et al.,
2015a), an open question remains on whether it is possible to close this gap.

Moreover, compared to the definition of differential privacy, there is a much
stricter definition of privacy guarantee known as _local differential privacy
(LDP)_. Under LDP, the data has to be injected with noise before collecting
the data and thus it does not need a trusted center, which results in a
stronger privacy guarantee. There are work on the design of bandit algorithms
under LDP (Chen et al., 2020; Ren et al., 2020). However, in combinatorial
(including cascading) bandits, if one directly injects noise to the data and
modifies the algorithm in each round as before, the regret scales as
$\mathcal{O}(K^{2})$, where $K$ is the maximum number of chosen arms in each
round. This is a notorious side-effect. In the work of Chen et al. (2020) for
combinatorial bandits, they discard information in each round that does not
influence the order of the regret to avoid the dependence on $K^{2}$.
Nevertheless, in real applications, the data is scarce and valuable and need
to be well stored to be used in other information analysis tasks. In this
case, the natural problem to protect privacy without discarding data and still
enjoying a preferable regret bound remains open.

#### Our contribution:

In this paper, we overcome the difficulties and solve the problems. Under DP,
through analyzing the dominant term in the regret, we utilize the post-
processing lemma from Dwork et al. (2014) and a tighter bound for private
continual release from Chan et al. (2011), proving the
$\mathcal{O}(\log^{1+\xi}T)$ regret upper bound, for an arbitrarily small
$\xi$. This matches the lower bound up to a $\mathcal{O}(\log^{\xi}T)$ factor.
Under LDP, we relax the regret dependence on $K^{2}$ through the balance
between privacy budget $\epsilon$ and error probability $\delta$. This holds
for both Laplace mechanism by analyses on composition and Gaussian mechanism.
The main contributions of this paper are summarized as follows:

  * •

For the cascading bandit problem under $\epsilon$-DP, we propose novel
algorithms with regret bound of $\mathcal{O}((\frac{L\log
T}{\epsilon})^{1+\xi})$. It matches the lower bound up to an arbitrary small
poly-log factor.

  * •

For the cascading bandit problem under ($\epsilon,\delta)$-LDP, we propose two
algorithms upper bounded by $\mathcal{O}(\frac{K\log 1/\delta\log
T}{\epsilon^{2}})$ which do not discard information. This holds for both
Laplace mechanism and Gaussian mechanism.

  * •

We extend our mechanism to combinatorial semi-bandit and proved a
$\mathcal{O}(\frac{K\log 1/\delta\log T}{\epsilon^{2}})$ regret, which is of
the same order of the regret bound as we achieved in the cascading bandit
setting under LDP.

  * •

We give two lower bounds, $\Omega(\frac{(L-K)\log T}{\Delta\epsilon^{2}})$ and
$\Omega((\frac{1}{\Delta}+\frac{1}{\epsilon})(L-K)\log T)$, for cascading
bandits under LDP and DP, respectively.

##  2 Related work

#### Cascading bandit

The cascading bandits problem was first proposed by Kveton et al. (2015a), in
which a $\mathcal{O}(\log T)$ upper bound by UCB-based methods and a matching
lower bound were presented. This problem is then extended to its linear
variant by Zong et al. (2016), in which a norm bound for contexts from Abbasi-
Yadkori et al. (2011) is employed and a $\mathcal{\tilde{O}}(Kd\sqrt{T})$
upper bound is presented. The combinatorial semi-bandit, which resembles
cascading bandit in many aspects is first introduced by Chen et al. (2013).
They also give corresponding $\mathcal{O}(K\log T)$ upper bound.

#### Differential privacy

Chan et al. (2011) first study the private continual release of statistics,
which provides the basis for research for multi-armed bandits. Mishra and
Thakurta (2015) give an $\mathcal{O}(\frac{K\log^{3}T}{\epsilon})$ upper bound
for the differential private bandit for the first time, where $K$ is the
number of arms. Tossou and Dimitrakakis (2016) tighten the upper bound to
$\mathcal{O}(\log T)$ but under a relaxed definition of privacy. Tossou and
Dimitrakakis (2017) also study the adversarial bandit under differential
privacy and give a first $\mathcal{O}(\frac{\sqrt{T}\log T}{\epsilon})$ upper
regret bound. Shariff and Sheffet (2018) give first lower bound for multi-
armed bandit with DP. Basu et al. (2019) give essential lower bounds for
different privacy definitions.

#### Local differential privacy

Under LDP, Ren et al. (2020) use the Laplace noise and provide the first
$\mathcal{O}(\frac{\log T}{\epsilon^{2}})$ upper bound for the multi-armed
bandit. Chen et al. (2020) study the combinatorial semi-bandit under LDP and
give the first $\mathcal{O}(\frac{\log T}{\epsilon^{2}})$ regret bound for the
combinatorial bandit. They use the trick, each round only update the worse arm
in the group, to avoid dependency on $K$, which is the size of each round’s
chosen arms.

##  3 Problem formulation

###  3.1 Cascading bandit

A cascading bandit problem can be denoted by a tuple $B=(E,P,K)$, where
$E=\\{1,...,L\\}$ is a set of $L$ base items, $P$ is a probability
distribution over $[0,1]^{E}$ and its expectation is $(\bar{w})_{i=1}^{L}$.
$K\leq L$ represents the number of recommended items each time. Through a time
horizon of $T$, at each round $t$, $w_{t}\in[0,1]^{E}$ is instant Bernoulli
reward drawn from $P$. It indicates user’s preference by $w_{t}(e)=1$ if and
only if item $e$ attracts user at time $t$.

The problem proceeds iteratively, at each round $t$, the algorithm is asked to
recommend a list of items
$A_{t}=(a_{1}^{t},a_{2}^{t},...,a_{K}^{t})\in\Pi_{K}(E)$. When the users
receive the recommended list, he reviews the list from the top and stop at
first attractive item $C_{t}$. The feedback to the algorithm is
$(w_{t})_{i=1}^{C_{t}}$, where $C_{t}=\arg\min\\{1\leq k\leq
K:w_{t}(a_{k}^{t})=1\\}$ with the assumption that $\arg\min\emptyset=\infty$.
The reward function $f(A,w)=1-\prod_{k=1}^{K}(1-w(a_{k}))$. Note that,
$w_{t}(a_{k}^{t})=\mathbbm{1}\\{C_{t}=k\\}\quad k=1,...,\min\\{C_{t},K\\}.$ We
say item $e$ is observed at time $t$ if $e=a_{k}^{t}$ for some $1\leq
k\leq\min\\{C_{t},K\\}$. The cumulative regret $R(T)$ is defined as

$\forall T>1,\quad R(T)=\mathbb{E}[\sum_{t=1}^{T}R(A_{t},w_{t})]\,,$

where $R(A_{t},w_{t})=f(A^{\ast},w_{t})-f(A_{t},w_{t})$ is the instant
stochastic regret at time $t$ and
$A^{\ast}={\arg\max}_{A\in\Pi_{K}(E)}f(A,\bar{w})\,.$ Next, we maintain two
mild assumptions that are common among cascading bandits literature (Kveton et
al., 2015a).

######  Assumption 1.

The weights $w$ are distributed as, $P(w)=\prod_{e\in E}P_{e}(w(e))\,,$ where
$P_{e}$ is a Bernoulli distribution with mean $\bar{w}(e)\,$.

######  Assumption 2.

The optimal action is unique, i.e. $\Delta_{min}=\min_{e\in[L]\backslash
A^{\ast}}\\{\bar{w}^{\ast}-\bar{w}(e)\\}>0\,.$

With Assumption 1, one can easily verify that
$\mathbb{E}[f(A,w)]=f(A,\bar{w})$. This make it possible to decompose the
regret to a solvable form. The Assumption 2 is necessary for any problem-
dependent regrets. Without loss of generality, for all proofs, we assume
$w_{1}\geq w_{2}\geq...\geq w_{L}$.

###  3.2 (Locally) differential privacy

We study the problem of cascading bandits under both the classic
$(\epsilon,\delta)$-differential privacy definition and
$(\epsilon,\delta)$-local differential privacy. We first give the rigorous
definition of differential privacy.

######  Definition 1 (Differential Privacy).

Let $D=\langle x_{1},x_{2},\dots,x_{T}\rangle$ be a sequence of data with
domain $X^{T}$. Let $A(D)=Y$, where $Y=\langle
y_{1},y_{2},\dots,y_{T}\rangle\in Y^{T}$ be $T$ outputs of the randomized
algorithm $A$ on input $D$. $A$ is said to preserve
$(\epsilon,\delta)$-differential privacy, if for any two data sequences
$D,D^{\prime}$ that differ in at most one entry, and for any subset $U\subset
Y^{T}$, it holds that

$P(A(D)\in U)\leq e^{\epsilon}\cdot P(A(D^{\prime})\in U)+\delta\,.$

If $\delta=0$, then we say the algorithm satisfies $\epsilon$-differential
privacy.

The local differential privacy model requires masking data with noise before
the accumulation of data in order to circumvent the need of a trusted center,
which leads to a more promising privacy guarantee. Formally, the
$(\epsilon,\delta)$-local differential privacy is defined as follows.

######  Definition 2 (Local Differential Privacy).

A mechanism $A:X\rightarrow Y$ is said to be $(\epsilon,\delta)$-local
differential private or $(\epsilon,\delta)$-LDP, if for any $x,x^{\prime}\in
X$, and any (measurable) subset $U\subset Y$, there is

$\displaystyle P(A(x)\in U)\leqslant e^{\epsilon}\cdot P(A(x^{\prime})\in
U)+\delta\,.$

If $\delta=0$, then we say the algorithm satisfies $\epsilon$-local
differential privacy.

##  4 Cascading bandit under differential privacy

In this section, we study cascading bandit under DP. In this situation, each
round, the user’s click information is submitted to a database as a trusted
center. When the algorithm needs data each round, it receives the noisy data
from the database.

The difficulty of this problem is governed by the control of the overall
injected noise in the stream data. Allocating the injected noise and adjusting
the confidence bound in the algorithm to guarantee better regret is the core
in this problem. In the previous work, people use a tree-based mechanism or
hybrid mechanism from Chan et al. (2011) to maintain the privacy of the stream
data in the MAB setting. It means constructing a tree based on previous data
to have a logarithmic number of sum when adding noise. This can control all
noises to an acceptable content. However, people either not use best
confidence bound or improperly construct the tree over stream, leading to some
sub-optimal regret bounds.

In this paper, through careful consideration, we find the order of the regret
in the bandit algorithm is dominated by the sequence length of the constructed
segment tree. If we see each round’s data as a $K$ length vector such as Chen
et al. (2020), then the sequence length is related to time $t$. In this case,
it is unavoidable with the $\log^{2.5}t$ by direct derivation from the utility
bound of the hybrid mechanism. It is hard to accept. Nonetheless, if the
sequence length is relevant with the number of each arm $T_{i}$ rather than
time $t$, we prove that the overall regret can be bounded by $\log^{1+\xi}t$
regret by a common inequality. In this work, we utilize the post-processing
lemma well-known in differential privacy, converting the privacy guarantee of
algorithm’s output to $L$ arms. Then just equally distribute the privacy
budget to all $L$ arms. We can control the pulled numbers of any sub-optimal
arm to $\log^{1+\xi}t$, which is the dominant term in regret.

We now describe our algorithm under DP. It is inspired by Tossou and
Dimitrakakis (2016), but under a much stronger definition of privacy. First,
the agent receives data from hybrid mechanism and calculate the upper
confidence bound for each arm. Compared to classic UCB algorithm, we add an
extra additional term from the noise from the injected noise. The algorithm
then outputs $K$ arms. The agent of the algorithm sends chosen $K$ arms to
users. Finally, the users pull arms receiving rewards and insert the rewards
to the hybrid mechanism for each arm, respectively. Our method is depicted in
Algorithm 1.

Input: $\epsilon$, the differential privacy parameter

Instantiate $L$ Hybrid Mechanisms with $\epsilon^{\prime}=\frac{\epsilon}{L}$.

Observe $w_{0}$

$\forall e\in E:T_{0}(e)\leftarrow 1,\hat{w}_{1}(e)\leftarrow w_{0}(e).$

for  _$t=1,2,...,n$_ do

$\forall e\in E:U_{t}(e)=\hat{w}+\sqrt{\frac{1.5\log
t}{T_{t-1}(e)}}+\frac{3c_{1}L\log^{1.5}n\log t}{\epsilon T_{t-1}(e)}$

Let $a_{1}^{t},...,a_{K}^{t}$ be $K$ items with largest private UCBs.

$A_{t}\leftarrow(a_{1}^{t},...,a_{K}^{t})$

Observe click $C_{t}\in\\{1,...,K,\infty\\}$

for  _$k=1,...,\min\\{C_{t},K\\}$_ do

e $\leftarrow a_{k}^{t}$

$T_{t}(e)\leftarrow T_{t-1}(e)+1$

Insert $w_{t}(e)$ to the hybrid mechanism for arm e.

Algorithm 1 Cascading-UCB under DP.

Next, we introduce two important lemmas to support our algorithm and proof.

######  Lemma 1 (Chan et al. (2011), Utility Bound For Hybrid Mechanism).

In the continual release procedure, the hybrid mechanism preserves
$\epsilon$-differential privacy and with probability $1-\gamma$, the added
noise to the data at time $n$ satisfies following inequality:

$|Noise|\leq\frac{c_{1}\log^{1.5}n\log 1/\gamma}{\epsilon}\,,$

where $c_{1}$ is a constant.

######  Lemma 2 (Post-Processing Lemma).

If the sequence $(w_{t}(e))_{t=1}^{T_{e}}$ for all arm $e$ is
$\epsilon$-differentially private, then the Algorithm 1 is
$\epsilon$-differentially private.

Based on Lemma 1, we can construct high probability events that estimation
outside of this confidence interval happens with arbitrary small probability.
This is the basis of UCB algorithms. The Lemma 2 ensures Algorithm 1 is
$\epsilon$-differentially private.

######  Theorem 1.

Algorithm 1 guarantees $\epsilon$-DP.

######  Theorem 2.

The regret of Algorithm 1 is upper bounded by:

$R(T)\leq\sum_{e=K+1}^{L}\frac{192}{\Delta_{e,K}}\left(\frac{c_{1}L}{\epsilon}\log
T\right)^{1+\xi}+\frac{2\pi^{2}}{3}L+c_{2}=\mathcal{O}\left(\sum_{e=K+1}^{L}\left[\frac{L\log
T}{\epsilon}\right]^{1+\xi}\right)\,,$

where $\xi$ is an arbitrary small positive real value and $c_{1},c_{2}$ are
constants independent of the problem.

To the best of our knowledge, this is the first $\mathcal{O}(\log^{1+\xi}T)$
regret in the common definition of differential privacy. We greatly improve
the existing regret bound by the post-processing lemma and the utility bound
on hybrid mechanism. Judging from the regret, we get this better dependence on
$t$ at the cost of extra dependence on $L$. However, in view of time $t$’s
dominance in the bandit setting, we believe this is a great improvement
compared to before. Besides, our proof method has the universality. It can be
used in improving bound on other bandits model under differential privacy such
as combinatorial semi-bandit and basic MAB. We do not give them in this paper.

##  5 Cascading bandit under local differential privacy

Under local differential privacy, each round when the user browses through the
list, he directly sends noisy data to the database rather than sending
original data and let database inject noise. This circumvents the need of
trusted center, so it has much stronger privacy guarantee. In this situation,
we need to protect every output at time $t$ and let it satisfy
$(\epsilon,\delta)$-local differential privacy. In previous work, Chen et al.
(2020) discard much information each round to reduce the privacy budget in the
combinatorial semi-bandit. This is not practical as the importance of
information in the real world. Therefore, in this paper, we study if there
exists a method can both satisfy $(\epsilon,\delta)$-LDP and appreciable
regret not discarding information.

###  5.1 Warm up: Laplace mechanism

First, we use Laplace mechanism to provide LDP guarantee. Our algorithm is
based on previous non-private cascading bandit. In order to guarantee privacy
constraint, each round we have to inject noise to the data, so original
confidence interval is no longer applicable. Naturally, the confidence set has
to expand to adapt to the introduction to new Laplace noises. Then, we give
our method in Algorithm 2.

######  Theorem 3.

Algorithm 2 guarantees $\epsilon$-LDP.

######  Theorem 4.

The regret of Algorithm 2 in time horizon T is upper bounded by:

$R(T)\leq\sum_{e=K+1}^{L}\frac{4(\sqrt{1.5}+K/\epsilon\sqrt{24})^{2}}{\Delta_{e,K}}\log
T+\frac{2\pi^{2}}{3}L=\mathcal{O}\left(\sum_{e=K+1}^{L}\frac{K^{2}}{\epsilon^{2}\Delta_{e,K}}\log
T\right)\,.$

Next, we discuss the proof outline of Theorem 4: First, the expected mean
outside the confidence set is bounded by a small probability because of the
sub-Gaussian property of two noises. Then we just consider event in high-
probability set. The upper confidence bound has a $\frac{K}{\epsilon}$ factor
because of Laplace noise. Then follow the same procedure as non-private
cascading bandit (Kveton et al., 2015a), we get
$T_{i}\leq\mathcal{O}(\frac{K^{2}\log T}{\epsilon^{2}})$ for all arm $i$.
Combing with the decomposed form of regret on account of nonlinear reward
function, the final regret is the weighted sum of all $T_{i}$. Thus the final
regret has $\mathcal{O}(\frac{K^{2}}{\epsilon^{2}})$ dependence.

Input: $\epsilon$: the differential privacy parameter,$K$: the maximum arm
each round recommends.

Initialization:

Observe $w_{0}$

$\forall e\in E:T_{0}(e)\leftarrow 1,\hat{w}_{1}(e)\leftarrow w_{0}(e)$

for  _$t=1,2,...,n$_ do

$\forall e\in E:U_{t}(e)=\hat{w}(e)+\sqrt{\frac{1.5\log
t}{T_{t-1}(e)}}+\frac{K}{\epsilon}\sqrt{\frac{24\log t}{T_{t-1}(e)}}$

Let $a_{1}^{t},...,a_{K}^{t}$ be $K$ items with largest private UCBs.

$A_{t}\leftarrow(a_{1}^{t},...,a_{K}^{t})$

Observe click $C_{t}\in\\{1,...,K,\infty\\}$

for  _$k=1,...,\min\\{C_{t},K\\}$_ do

e $\leftarrow a_{k}^{t}$

$T_{t}(e)\leftarrow T_{t-1}(e)+1$

$\hat{w}_{T_{e}(e)}(e)\leftarrow\frac{T_{t-1}(e)\hat{w}_{T_{t-1}(e)}(e)+\mathbbm{1}\\{C_{t}=k\\}+Lap(\frac{K}{\epsilon})}{T_{t}(e)}$

Algorithm 2 Cascading-UCB under LDP (Laplace Mechanism).

In our first given Laplace mechanism, the dependence on $K^{2}$ is a notorious
side-effect during the learning process. In recommender system, $K$ means the
recommended items to user and it is usually very large. In scenarios where
recommendation items come from a stream of information such as news feed, $K$
often tends to infinity. This leads to much larger regret. Therefore, a tough
work about reducing dependence on $K$ is in emergency. In subsection
(5.2)(5.3)(5.4), we make great efforts in reducing this dependence on $K$.

###  5.2 Improvement: Gaussian mechanism

The Laplace mechanism, though offering promising privacy protection, is
quadratically dependent on $K$. This thus makes the Laplace mechanism
impractical when $K$ is large. Previous solution to this catastrophic effect
is to discard information with negligible effect on the order of regret bound
(Chen et al., 2020). Despite the alleviation of the effect, this method is
inaccessible in many situations where data disposal is impossible. We now
present an improved algorithm to circumvent this dependency $K$ subtly, which
is based on the Gaussian mechanism.

Input: $\epsilon$: the differential privacy parameter,$K$: the maximum arm
each round recommends.

Initialization:$\sigma=\frac{1}{\epsilon}\sqrt{2K\ln\frac{1.25}{\delta}}$

Observe $w_{0}$.

$\forall e\in E:T_{0}(e)\leftarrow 1,\hat{w}_{1}(e)\leftarrow w_{0}(e).$

for  _$t=1,2,...,n$_ do

$\forall e\in E:U_{t}(e)=\hat{w}+\sqrt{\frac{1.5\log
t}{T_{t-1}(e)}}+\sigma\sqrt{\frac{2\log(2t^{3})}{T_{t-1}(e)}}$

Let $a_{1}^{t},...,a_{K}^{t}$ be $K$ items with largest private UCBs.

$A_{t}\leftarrow(a_{1}^{t},...,a_{K}^{t})$

Observe click $C_{t}\in\\{1,...,K,\infty\\}$

for  _$k=1,...,\min\\{C_{t},K\\}$_ do

e $\leftarrow a_{k}^{t}$

$T_{t}(e)\leftarrow T_{t-1}(e)+1$

$\hat{w}_{T_{e}(e)}(e)\leftarrow\frac{T_{t-1}(e)\hat{w}_{T_{t-1}(e)}(e)+\mathbbm{1}\\{C_{t}=k\\}+\mathcal{N}(0,\sigma^{2})}{T_{t}(e)}$

Algorithm 3 Cascading-UCB under LDP(Gaussian Mechanism).

The Gaussian mechanism, compared to Laplace mechanism, is sensitive to
$L_{2}$-norm instead of $L_{1}$-norm. This key property leads to our design of
a $\sqrt{K}$-dependent of upper confidence bound. The adjustment to the
confidence interval, directly lessen the dominating effect of the interval on
the regret bound and eliminate the $K^{2}$ dependency. We now give the
detailed algorithm description for Gaussian mechanism based cascading UCB
algorithm with LDP guarantee. Before going on our work, we first introduce a
lemma.

######  Lemma 3 (Zhao et al. (2019)).

Let $\Delta_{f}=\max\limits_{D,D^{\prime}}\|f(D)-f(D^{\prime})\|_{L_{2}}$,
then $\forall\delta\in(0,1)$, and
$\sigma>\frac{\Delta_{f}}{\epsilon}\sqrt{2\log\frac{1.25}{\delta}}$,$M(D)=f(D)+\mathcal{N}(0,\sigma^{2})$
satisfied $(\epsilon,\delta)$-differential privacy.

Lemma 3 gives the Gaussian mechanism privacy guarantee, if we inject
$\mathcal{N}(0,\sigma^{2})$ to reward of each item according to lemma. Based
on the concentration bound for Gaussian distribution, we get with probability
of at least $1-\gamma$, $u\in[\bar{X}-\sigma\sqrt{\frac{2\log
2/\gamma}{s}},\bar{X}+\sigma\sqrt{\frac{2\log 2/\gamma}{s}}]$. By the
concentration bound for Gaussian noise, we can use the Optimism in the Face of
Uncertainty principle to construct UCB-based method. The bias comes from two
noises: the noise from the Bernoulli distribution, this part we can control by
sub-Gaussian quality; the noise from the Gaussian noise due to the privacy
guarantee, this part can be controlled by the concentration bound for Gaussian
distribution. Then follow the same procedure as Laplace mechanism. Our method
is depicted in Algorithm 3.

######  Theorem 5.

Algorithm 3 guarantees $(\epsilon,\delta)$-LDP.

######  Theorem 6.

The regret of Algorithm 3 is upper bounded by:

$R(T)\leq\sum_{e=K+1}^{L}\frac{2(2\sqrt{1.5}+\frac{8}{\epsilon}\sqrt{K\log\frac{1.25}{\delta}})^{2}}{\Delta_{e,K}}\log
T=\mathcal{O}\left(\sum_{e=K+1}^{L}\frac{K}{\epsilon^{2}\Delta_{e,K}}\log
T\right).$

During the proof, the only position where the Gaussian mechanism is different
from the Laplace mechanism, is the confidence interval. We update the interval
to $\mathcal{O}(\frac{\sqrt{K}}{\epsilon})$ dependence based on concentration
bound for Gaussian distribution. As we have discussed in the above, the regret
has the linear dependence on $K$. It is a great improvement from the Laplace
mechanism. However, more fundamental reasons need to be explored to guide our
algorithm’s design.

###  5.3 Generalization: composition theorem

After careful investigation the regret of Gaussian mechanism, we identify a
trade-off between privacy budget $\epsilon$ and error probability $\delta$ in
regret. Comparing the regret of Gaussian mechanism and that of Laplace
mechanism, the dependence on privacy budget $\epsilon(\frac{\epsilon}{K})$ is
exchanged by an additional multiplicative $\delta(\log\frac{1}{\delta})$
regret. This motivation of exchanging for $\epsilon$ by a little $\delta$ is
just why advanced composition theorem in differential privacy is proposed.
Thus we can use this composition theorem at our situation to reduce the
dependence on $K$.

######  Lemma 4 (Kairouz et al. (2015), Corollary 4.1).

For any $\epsilon\in(0,0.9]$ and $\delta\in(0,1]$, if the database access
mechanism satisfies
$(\sqrt{\epsilon^{2}/4k\log(e+\epsilon/\delta)},\delta/2k)$-differential
privacy on each query output, then it satisfies
$(\epsilon,\delta)$-differential privacy under k-fold composition.

Before, we have to ensure every item $\frac{\epsilon}{K}$-indistinguishable.
Now, we just to ensure each item $\frac{\epsilon}{\sqrt{K}}$-indistinguishable
based on Lemma 4. Thus any $\epsilon$-dp mechanism can achieve half dependence
on $K$ at the cost of a $\log 1/\delta$ term in regret while ensuring their
$(\epsilon,\delta)$-local differential privacy. We use this composition
theorem in our situation. We give an illustrating example with the Laplace
mechanism to highlights the impact of the above theorem. By this theorem, we
can improve the regret of Laplace mechanism to $\mathcal{O}(K)$ dependence in
regret, which is the same as Gaussian mechanism.

######  Theorem 7.

Cascading-UCB algorithm using Laplace mechanism with parameter
$\epsilon^{\prime}=\frac{\epsilon}{\sqrt{4K\log(e+\epsilon/\delta)}}$ under
K-fold composition each round achieves $\mathcal{O}(\frac{K\log 1/\delta\log
T}{\epsilon^{2}})$ regret while ensuring $(\epsilon,\delta)$-local
differential privacy.

By the definition of DP, Laplace mechanism that attains $(\epsilon,0)$-DP is
also capable of offering $(\epsilon,\delta)$-DP protection. Using the
generalized theorem, every item observed in the list masked with a
$Lap(\frac{\sqrt{4K\log(e+\epsilon/\delta)}}{\epsilon})$ noise is enough to
guarantee $(\epsilon,\delta)$-dp. An UCB algorithm with confidence interval of
$\frac{4}{\epsilon}\sqrt{\frac{6K\log(e+\epsilon/\delta)\log
t}{T_{t-1}(e)}}+\sqrt{\frac{3\log t}{2T_{t-1}(e)}}$ then suffers only
$\mathcal{O}(\frac{K\log 1/\delta\log T}{\epsilon^{2}})$ regret while ensuring
privacy guarantee.

###  5.4 Relationship with combinatorial semi-bandit

Our proposed algorithms also shed light on privacy persevering bandits
algorithm under combinatorial semi-bandit, which holds great similarity with
cascading bandit set up. We take the Gaussian mechanism as an example and give
the following theorem on the regret upper bound of UCB algorithm under LDP
with combinatorial bandit, though we defer the detailed algorithm description
to appendix as Algorithm 4.

######  Theorem 8.

Algorithm 4 guarantees $(\epsilon,\delta)$-LDP.

######  Theorem 9.

The regret of Algorithm 4 is upper bounded by:

$R(T)\leq\left[\frac{128K\log\frac{1.25}{\delta}\log
T}{\min\\{\epsilon^{2},2\\}(f^{-1}(\Delta_{min}))^{2}}+\frac{\pi^{2}}{3}+1\right]m\Delta_{max}\,,$

where is $f$ is strictly increasing function satisfying $B_{\infty}$ bounded
smoothness and $K$ is maximum number of each round chosen arm.

##  6 Lower bounds

We now discuss the lower bound for cascading bandit under DP and LDP and the
optimality of our upper bounds. We first decompose the lower bound for
cascading bandit into a weighted sum of any sub-optimal arm’s pulled number.
Under LDP, this can be further converted into the KL-divergence of two arms
and thus implies a $\Omega(1/\epsilon^{2})$ dependence according to the
results from (Basu et al., 2019). Under DP, we decompose the number of any
sub-optimal arm into two parts: the number of pulls with no privacy guarantee
and the number of pulls with the cost of privacy. The following theorems
formalize our results.

######  Theorem 10.

For any cascading bandit of $\epsilon$-local differential privacy, the regret
of any consistent algorithm $R(T)$ is lower bounded by

$\displaystyle\liminf_{T\to\infty}\frac{R(T)}{\log
T}\geq\frac{(L-K)p(1-p)^{K}}{2\min\\{4,e^{2\epsilon}\\}(e^{\epsilon}-1)^{2}\Delta}\,.$

Note that when $p=1/K$ and $\epsilon\rightarrow 0$,
$\liminf_{T\to\infty}R(T)\geq\Omega(\frac{(L-K)}{\Delta\epsilon^{2}}\log T).$

######  Theorem 11.

For any cascading bandit of $\epsilon$-differential privacy, the regret of any
consistent algorithm $R(T)$ is lower bounded by

$R(T)\geq\Omega\left(\frac{(L-K)(1-p)^{K-1}\log
T}{\Delta}+\frac{(L-K)(1-p)^{K-1}\log T}{\epsilon}\right)\,.$

It can be observed that the definition of privacy protection, whether it is
differential privacy or local differential privacy, has negligible effect on
the lower bound of cascading bandits. Our proposed algorithm for cascading
bandits achieves matching upper bound under the LDP while there exists a
$\mathcal{O}(\log^{\xi}T)$ gap under DP.

##  7 Empirical results

In this section, we provide extensive empirical results that corroborate our
theoretical findings. We conduct experiments under DP and LDP for Gaussian and
Laplace mechanism with varying value of $\epsilon$. In order to highlight our
improvement, Laplace mechanism uses the form of Algorithm 2. The experiments
were proceeded with $L=20,K=4,\delta=10^{-3}$ unless other wise indicated. The
time horizon is set to $100000$ for all experiments. To sure reproducible
results, each experiment is repeated 10 times and averaged result is
presented. Without loss of generality, all noises are multiplied by 0.01 to
ensure most of the samples distributed among $[0,1]$.

#### Cascading bandits under local differential privacy.

The algorithms were analysed empirically under LDP with varying level of
$\epsilon$. Figure 1(a) 1(b), 1(c), 1(d) shows the cumulative regret incurred
by three algorithms mentioned with $\epsilon=\\{0.2,0.5,1,2\\}$. Laplace
based-UCB achieves the most cumulative regret among all algorithms analyzed.
Though non-private UCB incurred the lowest cumulative regret, the private
algorithms achieve regrets of order $\mathcal{O}(\log T)$ as well. Figure 1(e)
shows the performance of private algorithms varies according to various number
of $\epsilon$ in range of 0 to 2, where $\epsilon$ takes values of every 0.02
interval. When $\epsilon=0$, the regret is unaffordable for private algorithm.
However, as $\epsilon$ increases, the cumulative regret of the algorithms
quickly decays and soon achieve comparable cumulative regret with non private
algorithm, especially in the case of where Gaussian mechanism is applied. We
also test CUCB under $\epsilon=0.2$ and $\epsilon=2$ in figure 1(h), 1(i). It
can be observed that, when $\epsilon$ is set to relatively small value, the
gap between performance of private and non private algorithm is comparably
larger when $\epsilon$ is large.

(a) LDP,$\epsilon=0.2$

(b) LDP, $\epsilon=0.5$

(c) LDP, $\epsilon=1$

(d) LDP, $\epsilon=2$

(e) LDP, vary $\epsilon$

(f) DP, vary $\epsilon$

(g) DP, vary $L$

(h) CUCB under LDP, $\epsilon=0.2$

(i) CUCB under LDP, $\epsilon=2$

Figure 1: Empirical results for private and non private algorithms under LDP
and DP.

#### Cascading bandits under differential privacy.

We provide two sets of empirical results for cascading bandits under DP.
Figure 1(f) validates the algorithms under $\epsilon=\\{0.2,0.5,1,2\\}$. When
$\epsilon$ is taken to be a relatively larger value, the performance of
private algorithm is closer to the performance of non-private algorithm.
Figure 1(g) validates the private algorithms under varying number of arms, for
$L=\\{8,12,16,20\\}$. It can be observed that larger $L$ leads to larger
regret.

##  8 Conclusion and future work

In this paper, we study the differential privacy and local differential
privacy in the cascading bandit setting. Under DP, we give the state-of-the-
art $\mathcal{O}(\log^{1+\xi}T)$ regret in the common definition of DP. Under
LDP, we utilize the tradeoff between $\epsilon$ and $\delta$, relaxing the
$\mathcal{O}(K^{2})$ dependence to $\mathcal{O}(K)$. Two respective lower
bounds for both situations are provided. We conjecture the algorithm under DP
is not good enough to achieve the best regret. For example, during the
allocation of privacy budget, all previous work just equally distributes them.
However, distributing privacy budget based on arm’s difference may improve
regret order. We leave this direction for future work.

## References

  * Abadi et al. [2016] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016.
  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems_ , 2011.
  * Auer et al. [2002a] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2):235–256, 2002a.
  * Auer et al. [2002b] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002b.
  * Basu et al. [2019] Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou.  Differential privacy for multi-armed bandits: What is it and what is its cost?  _arXiv preprint arXiv:1905.12298_ , 2019.
  * Besbes et al. [2014] Omar Besbes, Yonatan Gur, and Assaf Zeevi.  Stochastic multi-armed-bandit problem with non-stationary rewards.  _Advances in neural information processing systems_ , 2014.
  * Bubeck and Cesa-Bianchi [2012] Sébastien Bubeck and Nicolò Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Found. Trends Mach. Learn._ , 5(1):1–122, 2012\.
  * Chan et al. [2011] T-H Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  _ACM Transactions on Information and System Security_ , 14(3):1–24, 2011.
  * Chen et al. [2013] Wei Chen, Yajun Wang, and Yang Yuan.  Combinatorial multi-armed bandit: General framework and applications.  In _International Conference on Machine Learning_ , 2013.
  * Chen et al. [2020] Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang, Wei Chen, and Liwei Wang.  (locally) differentially private combinatorial semi-bandits.  In _International Conference on Machine Learning_ , 2020.
  * Cheung et al. [2019] Wang Chi Cheung, Vincent Tan, and Zixin Zhong.  A thompson sampling algorithm for cascading bandits.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , 2019.
  * Dwork et al. [2006] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , 2006.
  * Dwork et al. [2010] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum.  Differential privacy under continual observation.  In _Proceedings of the forty-second ACM symposium on Theory of computing_ , 2010.
  * Dwork et al. [2014] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3-4):211–407, 2014.
  * Kairouz et al. [2015] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy.  In _International conference on machine learning_ , 2015.
  * Kveton et al. [2015a] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan.  Cascading bandits: Learning to rank in the cascade model.  In _International Conference on Machine Learning_ , 2015a.
  * Kveton et al. [2015b] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari.  Combinatorial cascading bandits.  In _Advances in Neural Information Processing Systems_ , 2015b.
  * Li et al. [2016] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen.  Contextual combinatorial cascading bandits.  In _International conference on machine learning_ , 2016.
  * Mishra and Thakurta [2015] Nikita Mishra and Abhradeep Thakurta.  (nearly) optimal differentially private stochastic multi-arm bandits.  In _Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence_ , 2015.
  * Ren et al. [2020] Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff.  Multi-armed bandits with local differential privacy.  _arXiv preprint arXiv:2007.03121_ , 2020.
  * Rigollet and Hütter [2015] Phillippe Rigollet and Jan-Christian Hütter.  High dimensional statistics.  _Lecture notes for course 18S997_ , 813:814, 2015.
  * Shariff and Sheffet [2018] Roshan Shariff and Or Sheffet.  Differentially private contextual linear bandits.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Tossou and Dimitrakakis [2016] Aristide Tossou and Christos Dimitrakakis.  Algorithms for differentially private multi-armed bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2016.
  * Tossou and Dimitrakakis [2017] Aristide Tossou and Christos Dimitrakakis.  Achieving privacy in the adversarial multi-armed bandit.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2017.
  * Wang et al. [2021] Kun Wang, Canzhe Zhao, Shuai Li, and Shuo Shao.  Conservative contextual combinatorial cascading bandit.  _arXiv preprint arXiv:2104.08615_ , 2021.
  * Zhao et al. [2019] Jun Zhao, Teng Wang, Tao Bai, Kwok-Yan Lam, Zhiying Xu, Shuyu Shi, Xuebin Ren, Xinyu Yang, Yang Liu, and Han Yu.  Reviewing and improving the gaussian mechanism for differential privacy.  _arXiv preprint arXiv:1911.12060_ , 2019.
  * Zong et al. [2016] Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton.  Cascading bandits for large-scale recommendation problems.  In _Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence_ , 2016.

##  Appendix A Technical Lemmas

######  Lemma 5 (Kveton et al. [2015a]).

For any item $e$ and optimal item $e^{\ast}$, let:
$G_{e,e^{\ast},t}=\\{\exists 1\leq k\leq K\quad s.t.\quad
a_{k}^{t}=e,\pi_{t}(k)=e^{\ast},w_{t}(a_{1}^{t})=...=w_{t}(a_{k-1}^{t})=0\\}$,
then there exists a permutation $\pi_{t}$ of optimal items $\\{1,...,K\\}$,
which is a deterministic function of $\mathcal{H}_{t}$, such that
$U_{t}(a^{t}_{k})\geq U_{t}(\pi_{t}(k))$ for all $k$ and the following holds:

$\displaystyle\mathbb{E}_{t}[R(A_{t},w_{t})]$
$\displaystyle\geq\alpha\sum_{e=K+1}^{L}\sum_{e^{\ast}=1}^{K}\Delta_{e,e^{\ast}}\mathbb{E}_{t}[\mathbbm{1}\\{G_{e,e^{\ast},t}\\}]\,,$
$\displaystyle\mathbb{E}_{t}[R(A_{t},w_{t})]$
$\displaystyle\leq\sum_{e=K+1}^{L}\sum_{e^{\ast}=1}^{K}\Delta_{e,e^{\ast}}\mathbb{E}_{t}[\mathbbm{1}\\{G_{e,e^{\ast},t}\\}]\,,$

where $\alpha=(1-\bar{w}(1))^{K-1}$ and $\bar{w}(1)$ is the attraction
probability of the most attractive item.

######  Lemma 6 (Chan et al. [2011]).

Let $X_{1},X_{2},...X_{n}$ be i.i.d. random variables following the Lap(b)
distribution and $Y=X_{1}+X_{2}+...+X_{n}$. For $v\geq b\sqrt{n}$ and
$0<\lambda<\frac{2\sqrt{2}v^{2}}{b}$, we have

$P\\{Y>\lambda\\}\leq\exp(-\frac{\lambda^{2}}{8v^{2}})\,.$

######  Lemma 7 (Rigollet and Hütter [2015]).

If $X_{1},...X_{n}$ are i.i.d $\mathcal{N}(u,\sigma^{2})$.
$\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}\sim\mathcal{N}(u,\sigma^{2}/n)$. The
following inequality holds:

$P(|\bar{X}-u|>t)\leq 2\exp(-\frac{nt^{2}}{2\sigma^{2}})\,.$

##  Appendix B CUCB under LDP

Input: $\epsilon$: the differential privacy parameter, $m$: the number of arm,
$K$: the maximum arm each round recommends.

Initialization:$\sigma=\frac{1}{\epsilon}\sqrt{2K\ln\frac{1.25}{\delta}},\gamma=2t^{-2}$

Observe $u_{0}$.

$\forall i\in[m]:T_{i}\leftarrow 1$

$\forall i\in[m]:\hat{u}(i)\leftarrow u_{0}(i)$

for  _$t=m+1,m+2,...,n$_ do

$\forall i\in[m]:\bar{u}_{i}=\hat{u}_{i}+\sqrt{\frac{3\log
t}{2T_{i}}}+\frac{2}{\epsilon}\sqrt{\frac{2K\log\frac{1.25}{\delta}\log
t}{T_{i}}}$

$S_{t}=\text{Oracle}(\bar{u}_{1},\bar{u}_{2},...,\bar{u}_{K})$.

Play S and observe $u_{t}$.

for  _$e=1,...,K$_ do

$T_{t}(e)=T_{t-1}(e)+1.$

$\hat{u}_{T_{t}(e)}(e)=\frac{T_{t-1}(e)\hat{u}_{T_{t-1}(e)}(e)+u_{t}(e)+\mathcal{N}(0,\sigma^{2})}{T_{t}(e)}$

Algorithm 4 CUCB under LDP (Gaussian Mechanism).

##  Appendix C Proof of Theorem 2

###### Proof.

According to Lemma 5, the instant regret at time $t$ satisfies following
inequality:

$R_{t}\leq\sum_{e=K+1}^{L}\sum_{e^{\ast}=1}^{K}\Delta_{e,e^{\ast}}\mathbb{E}_{t}[\mathbbm{1}\\{G_{e,e^{\ast},t}\\}]\,.$

Let $\tilde{w}$ denote the empirical mean not adding Laplace noise,
$\Lambda_{1,t}=\\{\forall e\in E,\text{ s.t. }|\bar{w}(e)-\tilde{w}(e)|\leq
c_{t,T_{t-1}(e)}\\}$, $\Lambda_{2,t}=\\{\forall e\in E,\text{ s.t.
}|\frac{Noise_{t,T_{t-1}(e)}}{T_{t-1}(e)}|\leq v_{t,T_{t-1}(e)}\\}$, and
$T_{t-1}(e)$ denotes the number of arm $e$ pulled until time $t-1$,

$\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{1,t}\\}]\leq\sum_{e\in
E}\sum_{t=1}^{T}\sum_{s=1}^{t}P(|\bar{w}(e)-\tilde{w}(e)|\geq c_{t,s})\leq
2\sum_{e\in E}\sum_{t=1}^{T}\sum_{s=1}^{t}e^{-3\log t}\leq 2\sum_{e\in
E}\sum_{t=1}^{T}t^{-2}\leq\frac{\pi^{2}}{3}L\,.$

Based on Lemma 1, let $\gamma=t^{-3}$, then
$v_{t,T_{t-1}(e)}=\frac{3c_{1}L\log^{1.5}T_{t-1}(e)\log t}{\epsilon
T_{t-1}(e)}$,

$\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{2,t}\\}]\leq\sum_{e\in
E}\sum_{t=1}^{T}\sum_{s=1}^{t}P(\left|\frac{Noise_{t,s}}{s}\right|\geq
v_{t,s})\leq\sum_{e\in E}\sum_{t=1}^{T}\sum_{s=1}^{t}t^{-3}\leq\sum_{e\in
E}\sum_{t=1}^{T}t^{-2}<\frac{\pi^{2}}{3}L\,.$
$R(T)\leq\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t}\\}R_{t}]+\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{1,t}\\}R_{t}]+\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{2,t}\\}R_{t}]\,.$

Then since $R_{t}\leq 1$, the last two terms can be bounded by
$\frac{2\pi^{2}}{3}L$, and for all time $t$ with probability of $1-t^{-3}$,

$\left|\frac{Noise_{t,T_{t-1}(e)}}{T_{t-1}(e)}\right|\leq\frac{3c_{1}L\log^{1.5}T_{t-1}(e)\log
t}{\epsilon T_{t-1}(e)}=v_{t,T_{t-1}(e)}\,.$

Therefore, the cumulative regret until time $T$ can be bounded as following:

$R(T)\leq\sum_{e=K+1}^{L}\mathbb{E}[\sum_{e^{\ast}=1}^{K}\sum_{t=1}^{T}\Delta_{e,e^{\ast}}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t},G_{e,e^{\ast},t}\\}]+\frac{2\pi^{2}L}{3}\,.$

If at time t, the algorithm selects a sup-optimal arm, then

$\bar{w}(e)+2c_{t-1,T_{t-1}(e)}+2v_{t-1,T_{t-1}(e)}\geq U_{t}(e)\geq
U_{t}(e^{\ast})\geq\bar{w}(e^{\ast})\,.$ $\Delta_{e,e^{\ast}}\leq
2c_{t-1,T_{t-1}(e)}+2v_{t-1,T_{t-1}(e)}\,.$

We consider its complementary set, i.e.
$\mathcal{E}_{t}=\\{\Delta_{e,e^{\ast}}>2c_{t-1,T_{t-1}(e)}+2v_{t-1,T_{t-1}(e)}\\}$.
It indicates the event the algorithm always chooses the optimal arm. It is
enough to bound the following two inequalities:

$\lambda_{0}\Delta>2c_{t,T_{t-1}(e)}\,,$
$(1-\lambda_{0})\Delta>2v_{t-1,T_{t-1}(e)}\,,$

For the first inequality, we get:

$T_{t-1}(e)\geq\frac{6}{\lambda_{0}^{2}\Delta_{e,e^{\ast}}^{2}}\log t\,.$

For the second inequality, we get:

$T_{t-1}(e)\geq B\log^{1.5}T_{t-1}(e)\,,$

where $B=\frac{6c_{1}L\log t}{\epsilon(1-\lambda)\Delta}$.
If we let $T_{t-1}(e)=B^{1+\xi}$, we get

$B^{\xi}\geq(1+\xi)^{1.5}\log^{1.5}B\,.$

When $t$ is sufficiently large, it must exist a constant $c_{2}$, when
$B>c_{2}$, the above inequality holds. Thus,

$T_{t-1}(e)\geq\max\\{\frac{6}{\lambda_{0}^{2}\Delta_{e,e^{\ast}}^{2}}\log
t,B^{1+\xi}\\}\,.$

It means that, when
$T_{t-1}(e)\geq\max\\{\frac{6}{\lambda_{0}^{2}\Delta_{e,e^{\ast}}^{2}}\log
t,B^{1+\xi}\\}$, the algorithm must choose the optimal arm at this time.
What’s more, we consider $t$ as the dominant term, and return back to previous
situation,

$\Delta_{e,e^{\ast}}\leq 2c_{t-1,T_{t-1}(e)}+2v_{t-1,T_{t-1}(e)}\Rightarrow
T_{t-1}(e)\leq B^{1+\xi}=\tau_{e,e^{\ast}}\,.$

Therefore,

$\displaystyle\sum_{e^{\ast}=1}^{K}\sum_{t=1}^{T}\Delta_{e,e^{\ast}}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t},G_{e,e^{\ast},t}\\}\leq\sum_{e^{\ast}=1}^{K}\Delta_{e,e^{\ast}}\sum_{t=1}^{T}\mathbbm{1}\\{T_{t-1}(e)\leq\tau_{e,e^{\ast}},G_{e,e^{\ast},t}\\}\,.$
(1)

Let

$M_{e,e^{\ast}}=\sum_{t=1}^{T}\mathbbm{1}\\{T_{t-1}(e)\leq\tau_{e,e^{\ast}},G_{e,e^{\ast},t}\\}.$

Now note that (i) the counter ${T}_{t-1}(e)$ of item $e$ increases by one when
the event $G_{e,e^{\ast},t}$ happens for any optimal item $e^{\ast}$, (ii) the
event $G_{e,e^{\ast},t}$ happens for at most one optimal $e^{\ast}$ at any
time $t$; and (iii) $\tau_{e,1}\leq...\leq\tau_{e,K}$. Based on these facts,
it follows that ${M}_{e,e^{\ast}}\leq\tau_{e,e^{\ast}}$, and moreover
$\sum_{e^{\ast}=1}^{K}{M}_{e,e^{\ast}}\leq\tau_{e,K}$. Therefore, the right-
hand side of (1) can be bounded by:

$\max\left\\{\sum_{e^{\ast}=1}^{K}\Delta_{e,e^{\ast}}m_{e,e^{\ast}}:0\leq
m_{e,e^{\ast}}\leq\tau_{e,e^{\ast}},\sum_{e^{\ast}=1}^{K}m_{e,e^{\ast}}\leq\tau_{e,K}\right\\}\,.$

Since the gaps are decreasing, $\Delta_{e,1}\geq\ldots\geq\Delta_{e,K}$, the
solution to the above problem is $m_{e,1}^{\ast}=\tau_{e,1}$,
$m_{e,2}^{\ast}=\tau_{e,2}-\tau_{e,1}$, $\dots$,
$m_{e,K}^{\ast}=\tau_{e,K}-\tau_{e,K-1}$. Therefore, the above can be bounded
by:

$\left[\Delta_{e,1}\frac{1}{\Delta_{e,1}^{1+\xi}}+\sum_{e^{\ast}=2}^{K}\Delta_{e,e^{\ast}}(\frac{1}{\Delta_{e,e^{\ast}}^{1+\xi}}-\frac{1}{\Delta_{e,e^{\ast}-1}^{1+\xi}})\right](\frac{\sqrt{8}c_{1}L}{\epsilon(1-\lambda_{0})}\ln
4T^{2})^{1+\xi}\,.$

Therefore, let $\lambda_{0}=1/2$, we get:

$\sum_{e^{\ast}=1}^{K}\sum_{t=1}^{T}\Delta_{e,e^{\ast}}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t},G_{e,e^{\ast},t}\\}\leq\frac{192c_{1}^{1+\xi}L^{1+\xi}}{\Delta_{e,K}^{\xi}\epsilon^{1+\xi}}\log^{1+\xi}T\,.$
$R(T)\leq\sum_{e=K+1}^{L}\frac{192c_{1}^{1+\xi}L^{1+\xi}}{\Delta_{e,K}\epsilon^{1+\xi}}\log^{1+\xi}T+\frac{2\pi^{2}}{3}L+c_{2}\,.\qed$

##  Appendix D Proof of Theorem 4

###### Proof.

Let $\tilde{w}$ denote the empirical mean not adding differential private
noise, $\Lambda_{1,t}=\\{\forall e\in E\text{ s.t.
}|\bar{w}(e)-\tilde{w}(e)|\leq c_{t,T_{t-1}(e)}\\}$, $\Lambda_{2,t}=\\{\forall
e\in E\text{ s.t.
}|\frac{\sum_{t=1}^{T_{t-1}(e)}Lap}{T_{t-1}(e)}|\leq\frac{K}{\epsilon}\sqrt{\frac{24\log
t}{T_{t-1}(e)}}\\}$, the cumulative regret until time $t$ is:

$R(T)\leq\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t}\\}R_{t}]+\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{1,t}\\}R_{t}]+\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{2,t}\\}R_{t}]\,.$
$\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{1,t}\\}]\leq\sum_{e\in
E}\sum_{t=1}^{T}\sum_{s=1}^{t}P(|\bar{w}(e)-\tilde{w}(e)|\geq c_{t,s})\leq
2\sum_{e\in E}\sum_{t=1}^{T}\sum_{s=1}^{t}e^{-3\log t}\leq 2\sum_{e\in
E}\sum_{t=1}^{T}t^{-2}\leq\frac{\pi^{2}}{3}L\,.$

According to Lemma 6, let $\lambda=\frac{K}{\epsilon}\sqrt{24s\log
t}$,$b=\frac{K}{\epsilon}$,$v=\frac{K\sqrt{s}}{\epsilon}$,$\lambda<\frac{2\sqrt{2}Ks}{\epsilon}$,
when $s\geq 3\log t$ (this part can be bounded by $3\log t$),

$\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{2,t}\\}]\leq\sum_{e\in
E}\sum_{t=1}^{T}\sum_{s=1}^{t}2P(\left|\frac{\sum_{t=1}^{s}Lap}{s}\right|\geq\frac{K}{\epsilon}\sqrt{\frac{24\log
t}{s}})\leq 2\sum_{e\in E}\sum_{t=1}^{T}\sum_{s=1}^{t}t^{-3}\leq 2\sum_{e\in
E}\sum_{t=1}^{T}t^{-2}\leq\frac{\pi^{2}}{3}L\,,$

Then based on Lemma 5, we get:

$\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t}\\}R_{t}]\leq\sum_{e=K+1}^{L}\Delta_{e,e^{\ast}}\mathbb{E}[\sum_{e^{\ast}=1}^{K}\sum_{t=1}^{T}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t},G_{e,e^{\ast},t}\\}]\,.$

Now we bound the above inequality for any sub-optimal arms, let
$h_{t-1,s}=\frac{K}{\epsilon}\sqrt{\frac{24\log t}{s}}$, if at time $t$, the
algorithm selects a sub-optimal arm e, then:

$\bar{w}(e)+2c_{t-1,T_{t-1}(e)}+2h_{t-1,T_{t-1}(e)}\geq U_{t}(e)\geq
U_{t}(e^{\ast})\geq\bar{w}(e^{\ast})\,,$

which implies:

$\Delta_{e,e^{\ast}}\leq 2c_{t-1,T_{t-1}(e)}+2h_{t-1,T_{t-1}(e)}\,.$

Then for any sub-optimal arm $e$, we have:

$T_{t-1}(e)\leq\frac{4\log
t(\sqrt{1.5}+\frac{K}{\epsilon}\sqrt{24})^{2}}{\Delta_{e,e^{\ast}}^{2}}=\tau_{e,e^{\ast}}\,.$

Therefore,

$\displaystyle\sum_{e^{\ast}=1}^{K}\sum_{t=1}^{T}\Delta_{e,e^{\ast}}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t},G_{e,e^{\ast},t}\\}\leq\sum_{e^{\ast}=1}^{K}\Delta_{e,e^{\ast}}\sum_{t=1}^{T}\mathbbm{1}\\{T_{t-1}(e)\leq\tau_{e,e^{\ast}},G_{e,e^{\ast},t}\\}\,.$
(2)

Let

$M_{e,e^{\ast}}=\sum_{t=1}^{T}\mathbbm{1}\\{T_{t-1}(e)\leq\tau_{e,e^{\ast}},G_{e,e^{\ast},t}\\}$

Now note that (i) the counter ${T}_{t-1}(e)$ of item $e$ increases by one when
the event $G_{e,e^{\ast},t}$ happens for any optimal item $e^{\ast}$, (ii) the
event $G_{e,e^{\ast},t}$ happens for at most one optimal $e^{\ast}$ at any
time $t$; and (iii) $\tau_{e,1}\leq...\leq\tau_{e,K}$. Based on these facts,
it follows that ${M}_{e,e^{\ast}}\leq\tau_{e,e^{\ast}}$, and moreover
$\sum_{e^{\ast}=1}^{K}{M}_{e,e^{\ast}}\leq\tau_{e,K}$. Therefore, the right-
hand side of (2) can be bounded by:

$\max\left\\{\sum_{e^{\ast}=1}^{K}\Delta_{e,e^{\ast}}m_{e,e^{\ast}}:0\leq
m_{e,e^{\ast}}\leq\tau_{e,e^{\ast}},\sum_{e^{\ast}=1}^{K}m_{e,e^{\ast}}\leq\tau_{e,K}\right\\}\,.$

Since the gaps are decreasing, $\Delta_{e,1}\geq\ldots\geq\Delta_{e,K}$, the
solution to the above problem is $m_{e,1}^{\ast}=\tau_{e,1}$,
$m_{e,2}^{\ast}=\tau_{e,2}-\tau_{e,1}$, $\dots$,
$m_{e,K}^{\ast}=\tau_{e,K}-\tau_{e,K-1}$. Therefore, the above can be bounded
by:

$\displaystyle\left[\Delta_{e,1}\frac{1}{\Delta_{e,1}^{2}}+\sum_{e^{\ast}=2}^{K}\Delta_{e,e^{\ast}}\left(\frac{1}{\Delta_{e,e^{\ast}}^{2}}-\frac{1}{\Delta_{e,e^{\ast}-1}^{2}}\right)\right]4(\sqrt{1.5}+K/\epsilon\sqrt{24})^{2}\log
T\,.$

The above term is bounded by

$\frac{8(\sqrt{1.5}+\frac{K}{\epsilon}\sqrt{24})^{2}}{\Delta_{e,K}}\log T\,.$

Therefore,

$R(T)\leq\sum_{e=K+1}^{L}\frac{8(\sqrt{1.5}+\frac{K}{\epsilon}\sqrt{24})^{2}}{\Delta_{e,K}}\log
T+\frac{2\pi^{2}}{3}L=\mathcal{O}\left(\sum_{e=K+1}^{L}\frac{K^{2}}{\epsilon^{2}\Delta_{e,K}}\log
T\right)\,.\qed$

##  Appendix E Proof of Theorem 6

###### Proof.

Following the same procedure as Appendix D, let $\tilde{w}$ denote the
empirical mean not adding differential private noise,
$\Lambda_{1,t}=\\{\forall e\in E\text{ s.t. }|\bar{w}(e)-\tilde{w}(e)|\leq
c_{t,T_{t-1}(e)}\\}$, $\Lambda_{2,t}=\\{\forall e\in E\text{ s.t.
}|\frac{\sum_{t=1}^{T_{t-1}(e)}N_{t}}{T_{t-1}(e)}|\leq\frac{2}{\epsilon}\sqrt{\frac{K\log\frac{1.25}{\delta}\log\frac{2}{\gamma}}{T_{t-1}(e)}}\\}$.

$R(T)\leq\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t}\\}R_{t}]+\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{1,t}\\}R_{t}]+\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\bar{\Lambda}_{2,t}\\}R_{t}]\,.$

Based on Lemma 7, we get with probability at least $1-\gamma$,
$u\in[\bar{X}-\frac{2}{\epsilon}\sqrt{\frac{K\log\frac{1.25}{\delta}\log\frac{2}{\gamma}}{T_{t-1}(e)}},\bar{X}+\frac{2}{\epsilon}\sqrt{\frac{K\log\frac{1.25}{\delta}\log\frac{2}{\gamma}}{T_{t-1}(e)}}]$.
Let error probability for Gaussian distribution $\gamma=t^{-3}$, then the
latter two terms can be bounded by $\frac{2\pi^{2}}{3}L$. As for the first
term,

$\mathbb{E}[\sum_{t=1}^{T}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t}\\}R_{t}]\leq\sum_{e=K+1}^{L}\Delta_{e,e^{\ast}}\mathbb{E}[\sum_{e^{\ast}=1}^{K}\sum_{t=1}^{T}\mathbbm{1}\\{\Lambda_{1,t},\Lambda_{2,t},G_{e,e^{\ast},t}\\}]\,.$

Let $h_{t-1,s}=\frac{2}{\epsilon}\sqrt{\frac{K\log\frac{1.25}{\delta}\log
2t^{3}}{s}}$, if the algorithm chooses a sub-optimal arm at round $t$,

$\bar{w}(e)+2c_{t-1,T_{t-1}(e)}+2h_{t-1,T_{t-1}(e)}\geq U_{t}(e)\geq
U_{t}(e^{\ast})\geq\bar{w}(e^{\ast})\,,$
$2c_{t-1,T_{t-1}(e)}+2h_{t-1,T_{t-1}(e)}\geq\Delta_{e,e^{\ast}}\,.$
$2\sqrt{\frac{1.5\log
t}{T_{t-1}(e)}}+\frac{4}{\epsilon}\sqrt{\frac{K\log\frac{1.25}{\delta}\log
2t^{3}}{T_{t-1}(e)}}\geq\Delta_{e,e^{\ast}}\,.$

Then we get,

$T_{t-1}(e)\leq\frac{(2\sqrt{1.5}+\frac{8}{\epsilon}\sqrt{K\log\frac{1.25}{\delta}})^{2}\log
t}{\Delta_{e,e^{\ast}}^{2}}\,.$

Follow the same procedure as Appendix D, finally we get:

$R(T)\leq\sum_{e=K+1}^{L}\frac{2(2\sqrt{1.5}+\frac{8}{\epsilon}\sqrt{K\log\frac{1.25}{\delta}})^{2}}{\Delta_{e,K}}\log
T+\frac{2\pi^{2}}{3}L=\mathcal{O}\left(\sum_{e=K+1}^{L}\frac{K\log
1/\delta}{\epsilon^{2}\Delta_{e,K}}\log T\right)\,.\qed$

##  Appendix F Proof of Theorem 9

###### Proof.

Before the proof, we first define some notations based on Chen et al. [2013]:
let $T_{i,t}$ be the number of arm $i$ pulled at the end of time $t$. The
oracle in the algorithm is a $(\alpha,\beta)$-approximation oracle, which
means $P[r_{u}(S)\geq\alpha\text{opt}_{u}]\geq\beta$. A super arm $S$ is bad
if $r_{u}(S)<\alpha\text{opt}_{u}$. And let
$S_{B}=\\{S|r_{u}(S)<\alpha\text{opt}_{u}\\}$. Under this circumstance,

$\Delta_{min}^{i}=\alpha\text{opt}_{u}-\max\\{r_{u}(S)|S\in S_{B},i\in S\\},$
$\Delta_{max}^{i}=\alpha\text{opt}_{u}-\min\\{r_{u}(S)|S\in S_{B},i\in
S\\}.\\\ $

Following above, the cumulative regret has the following form:

$R(T)=T\alpha\beta\text{opt}_{u}-\mathbb{E}[\sum_{i=1}^{T}r_{u}(S_{t})]$

Round $t$ is bad if the oracle selects a bad super arm $S_{t}\in S_{B}$. Let
$F_{t}$ be the event that the oracle fails to produce an $\alpha$-approximate
answer. We have $P[F_{t}]\leq 1-\beta$. Moreover, we maintain counter $N_{i}$
for each arm $i$ after $m$ initialization rounds. If at round $t\geq m$, the
oracle selects a bad super arm, let $i=\arg\min_{j\in S_{t}}N_{j,t-1}$, then
$N_{i,t}=N_{i,t-1}+1$. By definition, $N_{i,t}\leq T_{i,t}$. Note that in
every bad round, exactly one counter in $\\{N_{i}\\}_{i=1}^{m}$ is
incremented, so the total number of bad rounds in the first $T$ rounds is less
than or equal $\sum_{i}N_{i,T}$.

Let $l_{t}=\frac{128K\log\frac{1.25}{\delta}\log
t}{\min\\{\epsilon^{2},2\\}(f^{-1}(\Delta_{min}))^{2}}$. Consider a bad round
$t$, i.e. $S_{t}\in S_{B}$ is selected at time $t$, then we have:

$\displaystyle\quad\sum_{i=1}^{m}N_{i,T}-m(l_{T}+1)$ (3)
$\displaystyle=\sum_{t=m+1}^{T}\mathbbm{1}\\{S_{t}\in S_{B}\\}-ml_{T}$
$\displaystyle\leq\sum_{t=m+1}^{T}\sum_{i\in[m]}\mathbbm{1}\\{S_{t}\in
S_{B},N_{i,t}>N_{i,t-1},N_{i,t-1}>l_{T}\\}$
$\displaystyle\leq\sum_{t=m+1}^{T}\sum_{i\in[m]}\mathbbm{1}\\{S_{t}\in
S_{B},N_{i,t}>N_{i,t-1},N_{i,t-1}>l_{t}\\}$
$\displaystyle=\sum_{t=m+1}^{T}\mathbbm{1}\\{S_{t}\in S_{B},\forall i\in
S_{t},N_{i,t-1}>l_{t}\\}$
$\displaystyle\leq\sum_{t=m+1}^{T}(\mathbbm{1}\\{F_{t}\\}+\mathbbm{1}\\{\lnot
F_{t},S_{t}\in S_{B},\forall i\in S_{t},N_{i,t-1}>l_{t}\\})$
$\displaystyle\leq\sum_{t=m+1}^{T}(\mathbbm{1}\\{F_{t}\\}+\mathbbm{1}\\{\lnot
F_{t},S_{t}\in S_{B},\forall i\in S_{t},T_{i,t-1}>l_{t}\\})\,.$

Let $\tilde{u}$ denote the empirical mean not adding differential private
noise, and $G_{t}=\\{\forall
i\in[m],\left|\frac{\sum_{t}N_{t}}{T_{i}}\right|\leq\frac{2}{\epsilon}\sqrt{\frac{2K\log\frac{1.25}{\delta}\log
t}{T_{i}}}\\}$,

$\displaystyle P[|\tilde{u}_{i}-u_{i}|\geq\sqrt{3\log t/(2T_{i,t-1})}]$ (4)
$\displaystyle\leq\sum_{s=1}^{t-1}Pr[\\{|\hat{u}-u_{i}|\geqq\sqrt{3\log
t/(2s),T_{i,t-1}=s}\\}]$
$\displaystyle\leq\sum_{s=1}^{t-1}Pr[|\hat{u}_{i,s}-u_{i}|\geq\sqrt{3\log
t/(2s)}]$ $\displaystyle\leq 2te^{-3\log t}=2t^{-2}\,.$

Let $\gamma=2t^{-2}$, then with probability of $1-2t^{-2}$,

$\left|\frac{\sum_{t}N_{t}}{T_{i}}\right|\leq\frac{2}{\epsilon}\sqrt{\frac{2K\log\frac{1.25}{\delta}\log
t}{T_{i}}}\,.$

Let $\Lambda_{i,t}=2\sqrt{\frac{8K\log 1.25/\delta\log
t}{\min\\{\epsilon^{2},2\\}T_{i}}}$, then $\Lambda_{i,t}$ is the max
confidence interval each round because:

$\Lambda_{i,t}\geq\frac{2}{\epsilon}\sqrt{\frac{2K\log\frac{1.25}{\delta}\log
t}{T_{i}}}+\sqrt{\frac{3\log t}{2T_{i}}}\,.$

Let $E_{t}=\\{\forall
i\in[m],|\hat{u}_{i,T_{i,t-1}}-u_{i}|\leq\Lambda_{i,t}\\}$,
$\Lambda_{t}=\max\\{\Lambda_{i,t}|i\in S_{t}\\}$, $\Lambda=2\sqrt{\frac{8K\log
1.25/\delta\log t}{\min\\{\epsilon^{2},2\\}l_{t}}}$ which is not a random
variable, we have:

$P[\lnot E_{t}]\leq 4mt^{-2}\,,$

$E_{t}\Rightarrow\forall i\in S_{t},|\bar{u}_{i,t}-u_{i}|<2\Lambda_{t}\,,$

$\\{S_{t}\in S_{B},\forall i\in
S_{t},T_{i,t-1}>l_{t}\\}\Rightarrow\Lambda>\Lambda_{t}\,,$

$E_{t}\Rightarrow\bar{u}_{t}\geq u\,.$

If $\\{E_{t},\lnot F_{t},S_{t}\in S_{B},\forall i\in S_{t},T_{i,t-1}>l_{t}\\}$
holds at time $t$, we have the following important derivation:

$r_{u}(S_{t})+f(2\Lambda)>r_{u}(S_{t})+f(2\Lambda_{t})\geq
r_{\bar{u}_{t}}(S_{t})\geq\alpha\text{opt}_{\bar{u}_{t}}\geq\alpha
r_{\bar{u}_{t}}(S_{t}^{\ast})\geq r_{u}(S_{u}^{\ast})=\alpha\text{opt}_{u}\,.$

So we have

$r_{u}(S_{t})+f(2\Lambda)>\alpha\text{opt}_{u}\,.$

Since $l_{t}=\frac{128K\log\frac{1.25}{\delta}\log
t}{\min\\{\epsilon^{2},2\\}(f^{-1}(\Delta_{min}))^{2}}$, we have
$f(2\Lambda)=\Delta_{min}$. This contradicts the definition of $\Delta_{min}$
and the fact $S_{t}\in S_{B}$. Thus we have:

$\displaystyle P[\\{E_{t},\lnot F_{t},S_{t}\in S_{B},\forall i\in
S_{t},T_{i,t-1}>l_{t}\\}]=0\Rightarrow$ (5) $\displaystyle P[\\{\lnot
F_{t},S_{t}\in S_{B},\forall i\in S_{t},T_{i,t-1}>l_{t}\\}]\leq P[\lnot
E_{t}]\leq 4mt^{-2}\,.$ $\displaystyle\mathbb{E}[\sum_{i=1}^{m}N_{i,T}]\leq
m(l_{T}+1)+(1-\beta)(T-m)+\sum_{t=1}^{T}\frac{4m}{t^{2}}$ (6)
$\displaystyle\leq\frac{128mK\log\frac{1.25}{\delta}\log
T}{\min\\{\epsilon^{2},2\\}(f^{-1}(\Delta_{min}))^{2}}+(\frac{2\pi^{2}}{3}+1)m+(1-\beta)(T-m)\,.$
$\displaystyle R(T)$ $\displaystyle\leq
T\alpha\beta\text{opt}_{u}-(T\alpha\text{opt}_{u}-\mathbb{E}\left[\sum_{i=1}^{m}N_{i,T}\right]\Delta_{max})$
$\displaystyle\leq
T\alpha(\beta-1)\text{opt}_{u}+\mathbb{E}\left[\sum_{i=1}^{m}N_{i,T}\right]\Delta_{max}$
$\displaystyle\leq\left[\frac{128K\log\frac{1.25}{\delta}\log
T}{\min\\{\epsilon^{2},2\\}(f^{-1}(\Delta_{min}))^{2}}+\frac{2\pi^{2}}{3}+1\right]m\Delta_{max}$
$\displaystyle=\mathcal{O}\left(\frac{mK\log\frac{1}{\delta}\log
T}{\epsilon^{2}}\right)\,.\qed$

##  Appendix G Proof of Theorem 10

###### Proof.

Our lower bound is based on the following problem. There is $L$ items which
all obey the Bernoulli distribution $P$. Each arm’s weight is parameterized
by:

$\displaystyle\bar{w}(e)=\begin{cases}p&e\leq K\\\
p-\Delta&\text{otherwise}\,,\end{cases}$ (7)

where $\Delta\in(0,p)$. Based on Lemma 5,

$\mathbb{E}[R(A_{t},w_{t})]\geq\Delta(1-p)^{K-1}\sum_{e=K+1}^{L}\sum_{e^{\ast}=1}^{K}\mathbb{E}[\mathbbm{1}\\{G_{e,e^{\ast},t}\\}]\,.$

$\displaystyle R(n)$
$\displaystyle\geq\Delta(1-p)^{K-1}\sum_{e=K+1}^{L}\mathbb{E}[\sum_{t=1}^{n}\sum_{e^{\ast}=1}^{K}\mathbbm{1}\\{G_{e,e^{\ast},t}\\}]$
(8) $\displaystyle=\Delta(1-p)^{K-1}\sum_{e=K+1}^{L}\mathbb{E}[T_{n}(e)]\,.$

By the conclusion from the work of Theorem 4 in Basu et al. [2019], we have
that for any bandit

$\displaystyle\liminf_{n\to\infty}\frac{\mathbb{E}[T_{n}(e)]}{\log
n}\geq\frac{1}{2\min\\{4,e^{2\epsilon}\\}(e^{\epsilon}-1)^{2}d(p\|p-\Delta)}\,.$

Finally, using inequality $d(p\|p-\Delta)\leq\frac{\Delta^{2}}{p(1-p)}$, we
get the final bound:

$\liminf_{n\to\infty}\frac{R(n)}{\log
n}\geq\frac{(L-K)p(1-p)^{K}}{2\Delta\min\\{4,e^{2\epsilon}\\}(e^{\epsilon}-1)^{2}}\,.\qed$

##  Appendix H Proof of Theorem 11

###### Proof.

Our lower bound is based on the following problem. There is $L$ items which
all obey the Bernoulli distribution $P$. Each arm’s weight is parameterized
by:

$\displaystyle\bar{w}(e)=\begin{cases}p&e\leq K\\\
p-\Delta&\text{otherwise}\,,\end{cases}$ (9)

where $\Delta\in(0,p)$. According to Shariff and Sheffet [2018], the regret
lower bound of bandit under DP has to suffer two terms: one term comes from
the non-private bandit, one term comes from private bandit, as private
cascading bandit is strictly harder than non-private cascading bandit (by
reduction). The first term is at least $\Omega(\frac{(L-K)(1-p)^{K-1}\log
n}{\Delta})$(Kveton et al. [2015a]). Then we just have to prove cascading
bandit under DP suffers regret at least $\Omega(\frac{(L-K)(1-p)^{K-1}\log
n}{\epsilon})$.

$\displaystyle R(n)_{private}$
$\displaystyle\geq\sum_{t=1}^{n}\alpha\sum_{e=K+1}^{L}\sum_{e^{\ast}=1}^{K}\Delta_{e,e^{\ast}}\mathbb{E}_{t}[\mathbbm{1}\\{G_{e,e^{\ast},t}\\}]$
$\displaystyle\geq\Delta(1-p)^{K-1}\sum_{e=K+1}^{L}\mathbb{E}[T_{n}(e)]\,.$

Then according to Claim 14 from Shariff and Sheffet [2018], for any sub-
optimal arm, we get

$P\left[T_{n}(e)\geq\frac{\log n}{100\epsilon\Delta}\right]\geq\frac{1}{2}\,.$
$\mathbb{E}[T_{n}(e)]\geq\frac{1}{2}\times\frac{\log
n}{100\epsilon\Delta}=\frac{\log n}{200\epsilon\Delta}\,.$

So we get the conclusion:

$\displaystyle R(n)_{private}\geq\frac{(1-p)^{K-1}(L-K)\log
n}{200\epsilon}=\Omega(\frac{(L-K)(1-p)^{K-1}\log n}{\epsilon})\,.$

Therefore, we get the final form of the result. ∎

##  Appendix I Additional Experiments

(a) LDP,$K=4$ (b) LDP, $K=8$ (c) LDP, $K=12$ (d) LDP, $K=16$

Figure 2: Empirical results for private and non private algorithms under LDP
when $\epsilon=0.2$.

In this section, we supplement some experiments with different number of arms
under LDP. According to results, as $K$ increases, the gap between the Laplace
mechanism and Gaussian mechanism becomes larger. This phenomenon reflects the
influence of $K$ in the regret.


ifaamas [AAMAS ’24]Pre-print of paper accepted at 23rd International
Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024)May 6 – 10,
2024 Auckland, New ZealandN. Alechina, V. Dignum, M. Dastani, J.S. Sichman
(eds.) 2024 2024 1169 Federation University Australia Ballarat Australia
Lawrence Livermore National Laboratory Livermore USA University of Galway
Galway Ireland Deakin University Geelong Australia Linköping University
Linköping Sweden Universidade do Vale do Rio dos Sinos São Leopoldo Brazil
Vrije Universiteit Brussel Brussels Belgium

# Utility-Based Reinforcement Learning: Unifying Single-objective and Multi-
objective Reinforcement Learning

Peter Vamplew, Cameron Foale<EMAIL_ADDRESS>,  Conor F.
Hayes<EMAIL_ADDRESS>,  Patrick Mannion, Enda Howley
<EMAIL_ADDRESS><EMAIL_ADDRESS>,
Richard Dazeley, Scott Johnson<EMAIL_ADDRESS>,  Johan
Källström<EMAIL_ADDRESS>,  Gabriel Ramos<EMAIL_ADDRESS>and
Roxana Rădulescu, Willem Röpke, Diederik M. Roijers
<EMAIL_ADDRESS>
###### Abstract.

Research in multi-objective reinforcement learning (MORL) has introduced the
_utility-based_ paradigm, which makes use of both environmental rewards and a
function that defines the utility derived by the user from those rewards. In
this paper we extend this paradigm to the context of single-objective
reinforcement learning (RL), and outline multiple potential benefits including
the ability to perform multi-policy learning across tasks relating to
uncertain objectives, risk-aware RL, discounting, and safe RL. We also examine
the algorithmic implications of adopting a utility-based approach.

###### Key words and phrases:

reinforcement learning, utility

##  1\. Introduction

Multi-objective reinforcement learning (MORL) has emerged as an important sub-
field of reinforcement learning (RL) research Roijers et al. (2013); Hayes et
al. (2022a). So far the flow of knowledge has primarily been from conventional
single-objective RL (SORL) into MORL, with algorithmic innovations from SORL
being adapted to the context of multiple objectives Yang et al. (2019); Chen
et al. (2019); Alegre et al. (2022); Reymond et al. (2023). This paper runs
counter to that trend, as we will argue that the utility-based paradigm which
has been widely adopted in MORL Cai et al. (2023); Hayes et al. (2022a);
Rădulescu et al. (2020), has both relevance and benefits to SORL. We present a
general framework for utility-based RL (UBRL), which unifies the SORL and MORL
frameworks, and discuss benefits and potential applications of this for
single-objective problems – in particular focusing on the novel potential UBRL
offers for applying multi-policy learning to MDPs, thereby allowing greater
flexibility and decision-maker control over the behaviour of agents. We also
highlight lessons learned from MORL research regarding the algorithmic
implications of a utility-based approach as a guide to future single-objective
UBRL research and practice.

##  2\. Formalising utility-based RL

###  2.1. MDPs, MOMDPs and Optimisation criteria

SORL and MORL share a common foundation in the assumption that the environment
can be represented as some form of Markov Decision Process (MDP). In the
single objective case, a MDP is represented by the tuple $\langle
S,A,T,\gamma,\mu,R\rangle$, where:

  * •

$S$ is the state space

  * •

$A$ is the action space

  * •

$T\colon S\times A\times S\to\left[0,1\right]$ is a probabilistic transition
function

  * •

$\gamma\in[0,1)$ is a discount factor

  * •

$\mu\colon S\to[0,1]$ is a probability distribution over initial states

  * •

$R\colon S\times A\times S\to\mathbb{R}$ is a scalar-valued reward function

For a single-objective problem of this nature, the agent’s aim is to discover
a policy $\pi$ which maximises either the finite-horizon undiscounted reward
(Equation 1), the infinite-horizon cumulative discounted reward (Equation 2),
or the average reward (Equation 3). We note that the choice of criteria to
optimise is a decision made by the system designer, rather than being an
inherent property of the MDP itself.

$V_{\pi}=\mathbb{E}\left[\sum\limits^{N-1}_{i=0}r_{i}\>\middle|\>\pi,\mu\right]$
(1)

$V_{\pi}=\mathbb{E}\left[\sum\limits^{\infty}_{i=0}\gamma^{i}r_{i}\>\middle|\>\pi,\mu\right]$
(2)

$V_{\pi}=\lim_{N\rightarrow\infty}\frac{1}{N}\mathbb{E}\left[\sum\limits^{N-1}_{i=0}r_{i}\>\middle|\>\pi,\mu\right]$
(3)

MORL differs from SORL in being based on the concept of a Multi-Objective
Markov Decision Process (MOMDP). This is identical to a MDP in all respects
other than the reward, where rather than a scalar reward $R\colon S\times
A\times S\to\mathbb{R}$, the MOMDP has a vector-valued reward function
$\mathbf{R}:S\times A\times S\to\mathbb{R}^{d}$ which specifies the immediate
reward for each of the $d$ objectives.

The optimisation criteria in Equations 1–3 are insufficient for a MOMDP, as
they only provide a partial-ordering over the vector values. Therefore the
utility-based paradigm for MORL assumes the existence of a _utility function_
(sometimes called a _scalarisation function_) $u$, which maps the multi-
objective value of a policy to a scalar value Hayes et al. (2022a). Note that
the details of this utility function may or may not be available in advance –
in the latter case the agent may need to identify a set of policies which
would be optimal under different parameterisations of the utility function. We
will denote a parameterised utility function as $u_{\omega}$.

Given the existence of $u$ we can define two alternative optimisation
criteria, depending on the stage at which $u$ is applied (the reasoning for
this distinction will be discussed further in Section 5)111Note that these
equations relate to the infinite-horizon discounted return which has been the
most widely studied criteria in the MORL literature. Similar utility-based
equations can readily be defined for the finite-horizon and average-reward
criteria.. Equation 4 defines the scalarised expected reward (SER) where $u$
is applied to the expected vector reward, whereas Equation 5 defines the
expected scalarised reward, where $u$ is applied inside the expectation
operator. In either case, these equations provide a scalar value which defines
a total ordering over policies.

$V_{u}^{\pi}=u\left(\mathbb{E}\left[\sum\limits^{\infty}_{i=0}\gamma^{i}{\bf
r}_{i}\>\middle|\>\pi,\mu\right]\right)$ (4)

$V_{u}^{\pi}=\mathbb{E}\left[u\left(\sum\limits^{\infty}_{i=0}\gamma^{i}{\bf
r}_{i}\right)\>\middle|\>\pi,\mu\right]$ (5)

###  2.2. Utility-based RL as a general framework

In the previous subsection we highlighted the differences between conventional
single-objective RL and utility-based MORL. We now consider the commonalities
between these approaches, and argue that utility-based RL provides a general
framework which encompasses both SORL and MORL222The name ‘ _utility-based_ is
not intended to imply that standard SORL is _not_ maximising a measure of
utility, but to emphasise our framework’s _explicit_ consideration of user-
utility. In standard SORL the choice of optimisation criteria is made by the
developer whereas in multi-policy UBRL the final decision rests with the end-
user..

We start with the straightforward observation that MDPs are a subclass of
MOMDPs. Any MDP can be mapped to an equivalent MOMDP with a reward function
Which consists of a one-dimensional vector $\mathbf{R}=[R]$.

Having done this conversion, then utility-based methods such as those defined
in terms of the optimisation criteria in Equations 4 and 5 can be applied to
the resultant MOMDP. More generally we might consider any utility function
which maps from the expected mean rewards or the expected distribution of
rewards to a scalar value – we will explore examples of this in Sections 4.2
and 4.3. In addition the utility function may itself be parameterised, so that
a set of policies would be required in order to optimise the criteria across
all possible instantiations of $u$.

We note that some authors have previously criticised approaches such as MORL
and risk-aware RL as “special cases” Silver et al. (2021), and we anticipate
that similar criticisms may be levelled at UBRL. To the contrary, we argue
that the UBRL framework presented here is a strict generalisation of prior RL
frameworks. It can encompass standard scalar-reward RL by simply setting the
number of objectives $n$=1 and the utility function $u$ to the identity
function, while also supporting other more complex forms of RL, such as MORL.

##  3\. Motivation for utility-based SORL

While it is clear that SORL problems can be represented within the UBRL
framework, the question remains as to whether this is an unnecessary
complication, or whether it provides tangible benefits.

One advantage of a utility-based paradigm is that it can simplify the task of
reward engineering Dewey (2014) – that is, designing rewards in such a way
that maximising them induces the desired behaviour from an RL agent. In many
cases it may be easy to identify events (significant changes in state) within
the MDP for which rewards should be provided (e.g. picking up an object). But
the task of tailoring the magnitude of those rewards and the choice of
optimisation criteria to engender the desired behaviour is non-trivial (see
for example Knox et al. (2023)). Consider an environment with gold nuggets of
differing size at varying distances from the starting location. Whether an
agent prioritises collecting nearby low-value objects over more distant,
higher-valued objects will depend both on the relative magnitude of the
rewards and factors of the optimisation criteria, such as the choice of
discounting parameter. The utility-based framework separates the specification
of the rewards within the MDP (i.e. defining the environment) from the
definition of utility (i.e. defining the desired outcome), which may make the
reward engineer’s task easier.

This is particularly true when considered in light of experience in MORL
research which has found that a key benefit of a utility-based approach is
that it allows for the creation of multi-policy learning algorithms Hayes et
al. (2022a). Rather than aiming to learn a single policy optimal for a
specific definition of utility, multi-policy algorithms instead consider a set
of possible utility functions $U=\\{U_{1},..,U_{m}\\}$, and produce a
_coverage set_ of policies such that the agent has an optimal policy for every
member of $U$.

Learning multiple policies in this way is not possible within conventional
SORL, and so represents a novel contribution of the UBRL framework that
greatly enhances the RL process. We can define an MDP with a simple reward
structure, learn multiple policies for that MDP based on a variety of
different definitions of utility, and then select the utility function which
produces the most desirable outcomes. This will be significantly easier than
trying to specify _a priori_ the rewards required to produce the desired
behaviour. It also means that the final decision can be left in the hands of
the ultimate user of the system, rather than inappropriately requiring it to
be made by the system engineers Vamplew et al. (2022b). In addition this
provides flexibility should the desired behaviour change over time, as a new
policy can be selected without any need for further learning.

The benefits of multi-policy learning may also be realised at relatively
little additional cost. The utility-based approach allows for _inner-loop_
multi-policy methods, in which the multiple policies are learned in parallel
Hayes et al. (2022a). For example, the Conditioned Network algorithm trains a
single Deep Q-Network, conditioned on both the current MOMDP state and the
values of the parameters $\omega$ of the utility function. Experiences gained
while following the policy for one value of $\omega$ are leveraged to update
Q-values for policies conditioned on different values of $\omega$. This
greatly increases the sample-efficiency of these methods.

##  4\. Potential single-objective applications of utility-based RL

In this section we will discuss several potential applications of the utility-
based paradigm within SORL. These are intended as representative examples
where UBRL provides benefits, rather than an exhaustive list. These represent
both a reframing of existing concepts such as risk-aware RL to the UBRL
framework, as well as more novel concepts made possible by the adoption of
this framework.

###  4.1. Multi-policy methods for hard-to-define objectives

Consider the scenario of a mining company which has the choice between
carrying out its usual operations or following a riskier course of action that
can potentially lead to a lot of the resource being mined (e.g., committing
most of the workforce to exploratory excavation). The company has outstanding
contracts that commit it to sell a given amount to certain costumers at a set
price and leading to an incurred penalty if these amounts are not delivered.

There are various ways such a scenario might be addressed using standard RL
approaches:

  * •

We might model this as a constrained RL task Gattami et al. (2021), where the
fulfillment of contracts is treated as an inviolable constraint. But perhaps
this is overly restrictive, as the company management may be prepared to
breach contracts if the potential pay-off is sufficiently high?

  * •

It could be modelled as a SORL problem, with the value of the resource mined
represented as a positive scalar reward, and the penalty for unfulfilled
contracts as a negative reward. This would allow the agent to select the
riskier action if the potential gain offsets the contractual penalty. But such
an approach might fail to account for longer-term reputational damage arising
from unfulfilled contracts.

  * •

MORL methods could model the reputational harm as an additional objective to
be minimised. But this may be very difficult to define quantitatively.

As a result, the preferred approach of the company’s management might be to
generate a set of alternative policies using UBRL, and make an _a posteriori_
decision about which policy to follow. This could be accomplished by defining
the reward in terms of the quantity of the resource mined, and then specifying
the utility function as in Equation 6, where $d$ is the monetary value of each
unit of the resource, $c(\cdot)$ is a binary function returning 1 if the
contract terms are breached and 0 otherwise, $p$ is the penalty for breaching
the contract, and $h$ is an estimate of the financial impact of the
reputational harm caused by a contract breach.

$u_{h}=d*\sum\limits^{N-1}_{i=0}r_{i}-c(\sum\limits^{N-1}_{i=0}r_{i})*(p+h)\\\
$ (6)

Note that the utility term $u$ is conditioned on the value of $h$. Rather than
learning an optimal policy for a single estimate of cost of the reputational
harm, this utility-based formulation enables the UBRL agent to learn multiple
policies, each optimal with respect to a different estimated value of $h$. The
multiple policies produced via this process would then be presented to the
management, allowing them to make an informed decision about the best policy
to execute. Existing multi-policy MORL methods such as the Conditioned Network
approach of Abels et al. (2019) could readily be adapted to this task by
conditioning Q-values and policies on $h$.

###  4.2. Multi-policy risk-aware RL

Many authors have investigated risk-aware RL agents – that is, agents which
apply some awareness of risk during their decision-making rather than simply
aiming to maximise the expected return. A common approach to address this
problem is to use a distributional form of RL Bellemare et al. (2023); Hayes
et al. (2022b); Nguyen-Tang et al. (2021); Martin et al. (2020), which learns
the distribution of future returns from any state rather than just the mean
expected return. These approaches can take into account various aspects of
this distribution when identifying the optimal policy (e.g. best worst case,
more than 60% chance of profit, etc.) Cheng et al. (2023); Greenberg et al.
(2022); Yang et al. (2023); Fawzi et al. (2022); Hayes et al. (2023).

Again we would argue that such an approach is essentially already utility-
based. In this case the choice of constraints applied to the distribution
represents the definition of the utility function. Conventional SORL
approaches to risk-awareness assume that these constraints are fixed _a
priori_ , and learn a single policy which is optimal under those constraints.

In contrast by adopting the UBRL mindset, we can envisage an algorithm which
learns, in parallel using multi-policy methods, a set of policies which are
optimal under different risk-sensitivity preferences. These could then be
presented to a human decision-maker for selection of the policy to actually be
executed.

For example, consider the conditional value at risk (CVaR) defined in Equation
7, which has been widely-used as an optimisation criteria in risk-aware RL
Singh et al. (2020). Here $Z$ represents the distribution of future returns,
and $\alpha\in[0,1]$ is a parameter controlling the risk-sensitivity of the
agent. In conventional risk-aware RL, the value of $\alpha$ is fixed and a
single optimal policy is found. If we instead treat CVaRα as a utility
function parameterised by $\alpha$, we can apply multi-policy methods to find
policies with a diverse range of different sensitivities to risk, and then
allow a human decision-maker to select their preferred policy.

$\text{CVaR}_{\alpha}(Z)=\mathbb{E}\left[Z\>\middle|\>Z\leq\text{VaR}_{\alpha}(Z)\right]$
(7)

###  4.3. Multi-policy discounting

We noted earlier in Section 2 that the choice of optimisation criteria used in
SORL (undiscounted sum, discounted sum, or average reward) is made by the
system designer/user rather than being an inherent property of the MDP itself.
As such, this decision could in itself be regarded as a definition of user
utility, although it usually is not framed as such. Similarly we would contend
that the discounting term $\gamma$ used in Equation 2 can be viewed as a form
of utility definition. This term does not originate from the MDP itself, and
two agents using different discounting rates may well derive differing optimal
policies from the same MDP. Conventional SORL requires that the discounting
rate be fixed prior to learning, and the impact of this choice on the final
policy is not evident to the user. The only way to gain insight into the
effect of the discounting rate on the agent’s behaviour is to subsequently
train another agent on the same MDP using a different value for $\gamma$ which
is inefficient.

A superior approach is to treat the discounting rate as a parameter of the
utility function as shown in Equation 8, and use a multi-policy UBRL algorithm
to simultaneously learn optimal policies for a range of different values for
$\gamma$. The resulting policies can then be presented to the user, allowing
them to make a fully informed choice of the appropriate policy333We note that
the utility definition in Equation 8 differs from both forms of utility
previously used in MORL (Equations 4 and 5), in that it is the per-time-step
reward, rather than the summed return, that is being transformed.

$u_{\gamma}=\sum\limits^{\infty}_{i=0}\gamma^{i}r_{i}$ (8)

###  4.4. Satisficing agents

AI safety researchers have argued that ‘hard optimizers’ like conventional RL
can be unsafe, as their absolute focus on maximising the given reward signal
may lead to adverse side-effects if the rewards are not fully aligned with the
actual desired behaviour Taylor (2016); Vamplew et al. (2018). This has lead
to interest in developing _satisficing agents_ which are not incentivised to
over-optimise Hajiabolhassan and Ortner (2023). For example, in a multi-agent
resource-gathering task we might wish to disincentivise an agent from
collecting more resources than it actually needs to avoid adversely impacting
other agents. In the context of MORL satisficing has been implemented by
causing the agent to switch emphasis between objectives once a suitable level
of return has been achieved for each objective. This can either use a hard
threshold for each objective as in Vamplew et al. (2021) or a non-linear
utility which reduces the weighting for objectives as higher returns are
achieved Smith et al. (2023).

These approaches are not directly applicable to SORL due to the lack of
alternative objectives. For example, reducing the gradient of the utility
function as in Smith et al. (2023) would not disincentivise the agent from
still trying to maximise it. So for safe SORL we might need to consider the
concept of a non-monotonic utility function where the utility actually falls
in value after a satisfactory amount of reward has been received, as shown in
Equation 9.

$u_{\omega}=-\lvert\omega-\sum\limits^{\infty}_{i=0}\gamma^{i}r_{i}\rvert$ (9)

This could of course also be achieved via changing the reward definition
within the MDP. However that approach would not be amenable to multi-policy
learning whereas a multi-policy UBRL algorithm could simultaneously learn
optimal policies for various values of the threshold $\omega$, allowing
insight into the appropriate value of $\omega$ which will produce the desired
safe behaviour while still performing to a satisfactory level in terms of the
actual task.

##  5\. Implications of non-linear utility

The benefits of utility-based learning described earlier do not come without
some additional considerations. Research in utility-based MORL has identified
several issues which need to be taken into account when designing and applying
UBRL methods, particularly when using non-linear forms of $u$, such as that in
Equation 9.444While MORL research has considered both linear and non-linear
utility functions, we anticipate that single-objective UBRL will almost
exclusively use non-linear forms as applying a linear function to a scalar
reward merely scales the range of the reward without having any effect on the
optimal policy.

One fundamental issue relates to the selection of the optimisation criteria.
For tasks where we care about the outcome on a per-episode basis then the
Expected Scalarised Return (ESR) defined in Equation 5 is most appropriate,
whereas for problems where we care about the average outcome over multiple
episodes then Scalarised Expected Return (SER, Equation 4) is the correct
criteria555The distinction between ESR and SER does not arise in SORL or in
UBRL with linear $U$ as the values of Equations 4 and 5 are equal under those
settings.. Several researchers have reported that different algorithms may be
required to address the ESR and SER settings Rădulescu (2020); Roijers et al.
(2018); Vamplew et al. (2022a).

A non-linear utility function has further implications for value-based UBRL
algorithms, as it means the returns are no longer additive which is not
compatible with the Bellman equation Roijers et al. (2013). To address this,
UBRL algorithms based on temporal difference approaches may need to use an
_augmented state_ which concatenates the environment state with a history of
prior received rewards Vamplew et al. (2022a).

One further issue to consider is the implementation of reward shaping. In
SORL, shaping rewards are simply added to the MDP rewards prior to presenting
the reward to the agent. As long as certain conditions are met, the optimal
policy is not altered by the inclusion of these shaping rewards Ng et al.
(1999). However this may no longer be the case once a non-linear utility
function is applied to these combined reward values. To allow the agent to
appropriately evaluate the true utility, it may prove necessary to treat the
shaping reward as a separate objective Brys et al. (2014).

##  6\. Conclusion

The utility-based RL framework presented here unifies the previously disparate
areas of single-objective RL and multi-objective RL. The utility-based
approach increases the flexibility of SORL agents by facilitating multi-policy
learning. This is the main novel capability of UBRL compared to standard SORL,
and increases the control human decision-makers have over the RL agent, by
allowing them to make an informed selection of their preferred agent after
seeing which alternative behaviours exist, rather than making _a priori_
decisions regarding the reward design and optimisation criteria and hoping
these achieve the desired outcome. UBRL may also have benefits in terms of
simplifying the task of reward design. We have presented several motivating
cases where multi-policy UBRL approaches have advantages over standard SORL –
uncertain objectives, risk-aware RL, discounted returns, and satisficing
agents. Finally we believe that wide-spread adoption of UBRL as a unified
framework would facilitate faster and easier transfer of novel ideas,
algorithms and software implementations between the previously somewhat
disconnected fields of SORL and MORL.

## References

  * (1)
  * Abels et al. (2019) Axel Abels, Diederik Roijers, Tom Lenaerts, Ann Nowé, and Denis Steckelmacher. 2019\.  Dynamic weights in multi-objective deep reinforcement learning. In _International conference on machine learning_. PMLR, 11–20.
  * Alegre et al. (2022) Lucas Nunes Alegre, Ana Bazzan, and Bruno C Da Silva. 2022\.  Optimistic linear support and successor features as a basis for optimal policy transfer. In _International Conference on Machine Learning_. PMLR, 394–413.
  * Bellemare et al. (2023) Marc G Bellemare, Will Dabney, and Mark Rowland. 2023\.  _Distributional reinforcement learning_.  MIT Press.
  * Brys et al. (2014) Tim Brys, Anna Harutyunyan, Peter Vrancx, Matthew E Taylor, Daniel Kudenko, and Ann Nowé. 2014.  Multi-objectivization of reinforcement learning problems by reward shaping. In _2014 international joint conference on neural networks (IJCNN)_. IEEE, 2315–2322.
  * Cai et al. (2023) Xin-Qiang Cai, Pushi Zhang, Li Zhao, Jiang Bian, Masashi Sugiyama, and Ashley Juan Llorens. 2023.  Distributional Pareto-Optimal Multi-Objective Reinforcement Learning. In _Thirty-seventh Conference on Neural Information Processing Systems_.
  * Chen et al. (2019) Xi Chen, Ali Ghadirzadeh, Mårten Björkman, and Patric Jensfelt. 2019.  Meta-learning for multi-objective reinforcement learning. In _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 977–983.
  * Cheng et al. (2023) Ziteng Cheng, Sebastian Jaimungal, and Nick Martin. 2023\.  Distributional Method for Risk Averse Reinforcement Learning.  _arXiv preprint arXiv:2302.14109_ (2023).
  * Dewey (2014) Daniel Dewey. 2014\.  Reinforcement learning and the reward engineering principle. In _2014 AAAI Spring Symposium Series_.
  * Fawzi et al. (2022) Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, et al. 2022\.  Discovering faster matrix multiplication algorithms with reinforcement learning.  _Nature_ 610, 7930 (2022), 47–53.
  * Gattami et al. (2021) Ather Gattami, Qinbo Bai, and Vaneet Aggarwal. 2021.  Reinforcement learning for constrained markov decision processes. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 2656–2664.
  * Greenberg et al. (2022) Ido Greenberg, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. 2022.  Efficient risk-averse reinforcement learning.  _Advances in Neural Information Processing Systems_ 35 (2022), 32639–32652.
  * Hajiabolhassan and Ortner (2023) Hossein Hajiabolhassan and Ronald Ortner. 2023.  Online Regret Bounds for Satisficing in MDPs. In _Sixteenth European Workshop on Reinforcement Learning_.
  * Hayes et al. (2022a) Conor F Hayes, Roxana Rădulescu, Eugenio Bargiacchi, Johan Källström, Matthew Macfarlane, Mathieu Reymond, Timothy Verstraeten, Luisa M Zintgraf, Richard Dazeley, Fredrik Heintz, et al. 2022a.  A practical guide to multi-objective reinforcement learning and planning.  _Autonomous Agents and Multi-Agent Systems_ 36, 1 (2022), 26\.
  * Hayes et al. (2023) Conor F Hayes, Mathieu Reymond, Diederik M Roijers, Enda Howley, and Patrick Mannion. 2023\.  Monte Carlo tree search algorithms for risk-aware and multi-objective reinforcement learning.  _Autonomous Agents and Multi-Agent Systems_ 37, 2 (2023), 26\.
  * Hayes et al. (2022b) Conor F Hayes, Timothy Verstraeten, Diederik M Roijers, Enda Howley, and Patrick Mannion. 2022b.  Expected scalarised returns dominance: a new solution concept for multi-objective decision making.  _Neural Computing and Applications_ (2022), 1–21.
  * Knox et al. (2023) W Bradley Knox, Alessandro Allievi, Holger Banzhaf, Felix Schmitt, and Peter Stone. 2023.  Reward (mis) design for autonomous driving.  _Artificial Intelligence_ 316 (2023), 103829.
  * Martin et al. (2020) John Martin, Michal Lyskawinski, Xiaohu Li, and Brendan Englot. 2020.  Stochastically dominant distributional reinforcement learning. In _International conference on machine learning_. PMLR, 6745–6754.
  * Ng et al. (1999) Andrew Y Ng, Daishi Harada, and Stuart Russell. 1999\.  Policy invariance under reward transformations: Theory and application to reward shaping. In _Icml_ , Vol. 99. Citeseer, 278–287.
  * Nguyen-Tang et al. (2021) Thanh Nguyen-Tang, Sunil Gupta, and Svetha Venkatesh. 2021\.  Distributional reinforcement learning via moment matching. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 9144–9152.
  * Rădulescu (2020) Roxana Rădulescu. 2020\.  A Utility-Based Perspective on Multi-Objective Multi-Agent Decision Making. In _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. Auckland, New Zealand: AAMAS_. 2207–2208.
  * Rădulescu et al. (2020) Roxana Rădulescu, Patrick Mannion, Diederik M Roijers, and Ann Nowé. 2020.  Multi-objective multi-agent decision making: a utility-based analysis and survey.  _Autonomous Agents and Multi-Agent Systems_ 34, 1 (2020), 10\.
  * Reymond et al. (2023) Mathieu Reymond, Conor F Hayes, Denis Steckelmacher, Diederik M Roijers, and Ann Nowé. 2023\.  Actor-critic multi-objective reinforcement learning for non-linear utility functions.  _Autonomous Agents and Multi-Agent Systems_ 37, 2 (2023), 23\.
  * Roijers et al. (2018) Diederik M Roijers, Denis Steckelmacher, and Ann Nowé. 2018\.  Multi-objective reinforcement learning for the expected utility of the return. In _Proceedings of the Adaptive and Learning Agents workshop at FAIM_ , Vol. 2018.
  * Roijers et al. (2013) Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. 2013.  A survey of multi-objective sequential decision-making.  _Journal of Artificial Intelligence Research_ 48 (2013), 67–113.
  * Silver et al. (2021) David Silver, Satinder Singh, Doina Precup, and Richard S Sutton. 2021.  Reward Is Enough.  _Artificial Intelligence_ (2021), 103535.
  * Singh et al. (2020) Rahul Singh, Qinsheng Zhang, and Yongxin Chen. 2020\.  Improving robustness via risk averse distributional reinforcement learning. In _Learning for Dynamics and Control_. PMLR, 958–968.
  * Smith et al. (2023) Benjamin J Smith, Robert Klassert, and Roland Pihlakas. 2023\.  Using soft maximin for risk averse multi-objective decision-making.  _Autonomous Agents and Multi-Agent Systems_ 37, 1 (2023), 11\.
  * Taylor (2016) Jessica Taylor. 2016\.  Quantilizers: A Safer Alternative to Maximizers for Limited Optimization.. In _AAAI Workshop: AI, Ethics, and Society_.
  * Vamplew et al. (2018) Peter Vamplew, Richard Dazeley, Cameron Foale, Sally Firmin, and Jane Mummery. 2018.  Human-aligned artificial intelligence is a multiobjective problem.  _Ethics and Information Technology_ 20 (2018), 27–40.
  * Vamplew et al. (2022a) Peter Vamplew, Cameron Foale, and Richard Dazeley. 2022a.  The impact of environmental stochasticity on value-based multiobjective reinforcement learning.  _Neural Computing and Applications_ (2022), 1–17.
  * Vamplew et al. (2021) Peter Vamplew, Cameron Foale, Richard Dazeley, and Adam Bignold. 2021.  Potential-based multiobjective reinforcement learning approaches to low-impact agents for AI safety.  _Engineering Applications of Artificial Intelligence_ 100 (2021), 104186\.
  * Vamplew et al. (2022b) Peter Vamplew, Benjamin J Smith, Johan Källström, Gabriel Ramos, Roxana Rădulescu, Diederik M Roijers, Conor F Hayes, Fredrik Heintz, Patrick Mannion, Pieter JK Libin, et al. 2022b.  Scalar reward is not enough: A response to Silver, Singh, Precup and Sutton (2021).  _Autonomous Agents and Multi-Agent Systems_ 36, 2 (2022), 41\.
  * Yang et al. (2023) Qisong Yang, Thiago D Simão, Simon H Tindemans, and Matthijs TJ Spaan. 2023.  Safety-constrained reinforcement learning with a distributional safety critic.  _Machine Learning_ 112, 3 (2023), 859–887.
  * Yang et al. (2019) Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. 2019\.  A generalized algorithm for multi-objective reinforcement learning and policy adaptation.  _Advances in neural information processing systems_ 32 (2019).