#  Decentralized Learning for Multi-player Multi-armed Bandits ††thanks:
Dileep Kalathil, Naumaan Nayyar and Rahul Jain ((manisser,nnayyar,rahul.jain)
@usc.edu) are with the Department of Electrical Engineering, University of
Southern California, Los Angeles, CA, USA. This research is supported by AFOSR
grant FA9550-10-1-0307 and NSF CAREER award CNS-0954116.
††thanks: A preliminary version of this paper is under submission to IEEE CDC
2012. This version contains proofs of all theorems as well as new results on
Markovian MABs.

Dileep Kalathil, Naumaan Nayyar and Rahul Jain

###### Abstract

We consider the problem of distributed online learning with multiple players
in multi-armed bandits (MAB) models. Each player can pick among multiple arms.
When a player picks an arm, it gets a reward. We consider both i.i.d. reward
model and Markovian reward model. In the i.i.d. model each arm is modelled as
an i.i.d. process with an unknown distribution with an unknown mean. In the
Markovian model, each arm is modelled as a finite, irreducible, aperiodic and
reversible Markov chain with an unknown probability transition matrix and
stationary distribution. The arms give different rewards to different players.
If two players pick the same arm, there is a “collision”, and neither of them
get any reward. There is no dedicated control channel for coordination or
communication among the players. Any other communication between the users is
costly and will add to the regret. We propose an online index-based
distributed learning policy called ${\tt dUCB_{4}}$ algorithm that trades off
exploration v. exploitation in the right way, and achieves expected regret
that grows at most as near-$O(\log^{2}T)$. The motivation comes from
opportunistic spectrum access by multiple secondary users in cognitive radio
networks wherein they must pick among various wireless channels that look
different to different users. This is the first distributed learning algorithm
for multi-player MABs to the best of our knowledge.

###### Index Terms:

Distributed adaptive control, multi-armed bandit, online learning, multi-agent
systems.

##  I Introduction

In [1], Lai and Robbins introduced the classical non-Bayesian multi-armed
bandit model. Such models capture the essence of the learning problem that
players face in an unknown environment, where the players must not only
explore to learn but also exploit in choosing the best arm. Specifically,
suppose a player can choose between $N$ arms. Upon choosing an arm $i$, it
gets a reward from a distribution with density $f(x,\theta_{i})$. Time is
slotted, and players do not know the distributions (nor any statistics about
them). The problem is to find a learning policy that minimizes the expected
regret over some time horizon $T$. It was shown by Lai and Robbins [1] that
there exists an index-type policy that achieves expected regret that grows
asymptotically as $\log T$, and this is order-optimal, i.e., there exists no
causal policy that can do better. This was generalized by Anantharam, et al
[2] to the case of multiple plays, i.e., when the player can pick multiple
arms at the same time. In [3], Agrawal proposed a sample mean based index
policy which achieves $\log T$ regret asymptotically. Assuming that the
rewards are coming from a distribution of bounded support, Auer, et al [4]
proposed a much simpler sample mean based index policy, called ${\tt
UCB_{1}}$, which achieves $\log T$ uniformly over time, not only
asymptotically. Also, unlike the policy in [3], the index doesn’t depend on
the specific family of distributions that the rewards come from.

In [5], Anantharam, et al proposed a policy to the case where the arms are
modelled as Markovian, not i.i.d. The rewards are assumed to come from a
finite, irreducible and aperiodic Markov chain represented by a single
parameter probability transition matrix. The state of each arm evolves
according to an underlying transition probability matrix when the arm is
played and remains frozen when passive. Such problems are called _rested
Markovian bandit problems_ (where _rested_ refers to no state evolution until
the arm is played). In [6], Tenkin and Liu extended the ${\tt UCB_{1}}$ policy
to the case of rested Markovian bandit problems. If some non-trivial bounds on
the underlying Markov chains are known a priori, they showed that the policy
achieves $\log T$ regret uniformly over time. Also, if no information about
the underlying Markov chains is available, the policy can easily be modified
to get a _near_ -$O(\log T)$ regret asymptotically. The models in which the
state of an arm continues to evolve even when it is not played are called
_restless Markovian bandit problems_. Restless models are considerably more
difficult than the rested models and have been shown to be P-SPACE hard [7].
This is because the optimal policy no longer will be to “play the arm with the
highest mean reward”. [8] employs a weaker notion of regret (weak regret)
which compares the reward of a policy to that of a policy which always plays
the the arm with the highest mean reward. They propose a policy which achieves
$\log T$ (weak) regret uniformly over time if certain bounds on the underlying
Markov model are known a priori and achieves a near-$O(\log T)$ (weak) regret
asymptotically when no such knowledge is available. [9] proposes another
simpler policy which achieves the same bounds for weak regret. [10] proposes a
policy based on deterministic sequence of exploration and exploitation and
achieves the same bounds for weak regret. In [11], the authors consider the
notion of strong regret and propose a policy which achieves near-$\log T$
(strong) regret for some special cases of the restless model.

Recently, there is an increasing interest in multi-armed bandit models, partly
because of opportunistic spectrum access problems. Consider a user who must
choose between $N$ wireless channels. Yet, it knows nothing about the channel
statistics, i.e., has no idea of how good or bad the channels are, and what
rate it may expect to get from each channel. The rates could be learnt by
exploring various channels. Thus, these have been formulated as multi-armed
bandit problems, and index-type policies have been proposed for choosing
spectrum channels. In many scenarios, there are multiple users accessing the
channels at the same time. Each of these users must be matched to a different
channel. These have been formulated as a combinatorial multi-armed bandit
problem [12] [13], and it was shown that an “index-matching” algorithm that at
each instant determines a matching by solving a sum-index maximization problem
achieves $O(\log T)$ regret uniformly over time, and this is indeed order-
optimal.

In other settings, the users cannot coordinate, and the problem must be solved
in a decentralized manner. Thus, settings where all channels (arms) are
identical for all users with i.i.d. rewards have been considered, and index-
type policies that can achieve coordination have been proposed that get
$O(\log T)$ regret uniformly over time [14, 15, 16, 10]. A similar result for
Markovian reward model with weak regret has been shown by [10], assuming some
non-trivial bounds on the underlying Markov chains are known a priori. The
regret scales only polynomially in the number of users and channels.
Surprisingly, the lack of coordination between the players asymptotically
imposes no additional cost or regret.

In this paper, we consider the decentralized multi-armed bandit problem with
distinct arms for each players. We consider both the i.i.d. reward model and
the _rested_ Markovian reward model. All players together must discover the
best arms to play as a team. However, since they are all trying to learn at
the same time, they may collide when two or more pick the same arm. We propose
an index-type policy ${\tt dUCB_{4}}$ based on a variation of the ${\tt
UCB_{1}}$ index. At its’ heart is a distributed bipartite matching algorithm
such as Bertsekas’ auction algorithm [17]. This algorithm operates in rounds,
and in each round prices for various arms are determined based on bid-values.
This imposes communication (and computation) cost on the algorithm that must
be accounted for. Nevertheless, we show that when certain non-trivial bounds
on the model parameters are known a priori, the ${\tt dUCB_{4}}$ algorithm
that we introduce achieves (at most) near-$O(\log^{2}T)$ growth non-
asymptotically in expected regret. If no such information about the model
parameters are available, ${\tt dUCB_{4}}$ algorithm still achieves (at most)
near-$O(\log^{2}T)$ regret asymptotically. A lower bound, however, is not
known at this point, and a work in progress.

The paper is organized as follows. In Section II, we present the model and
problem formulation. In section III and IV we present some variations on
single player MAB with i.i.d. rewards and Markovian rewards respectively. In
section V, we introduce the decentralized MAB problem with i.i.d. rewards. We
then extend the results to the decentralized cases with Markovian rewards in
section VI. In section VII we present the distributed bipartite matching
algorithm which is used in our main algorithm for decentralized MAB. In
section VIII, we present some simulation results to numerically evaluate the
performance of our algorithm.

##  II Model and Problem Formulation

###  II-A Arms with i.i.d. rewards

We consider an $N$-armed bandit with $M$ players. In a wireless cognitive
radio setting [18], each arm could correspond to a channel, and each player to
a user who wants to use a channel. Time is slotted, and at each instant each
player picks an arm. There is no dedicated control channel for coordination
among the players. So, potentially more than one players can pick the same arm
at the same instant. We will regard that as a collision. Player $i$ playing
arm $k$ at time $t$ yields i.i.d. reward $S_{ik}(t)$ with univariate density
function $f(s,\theta_{ik})$, where $\theta_{ik}$ is a parameter in the set
$\Theta_{ik}$. We will assume that the rewards are bounded, and without loss
of generality lie in $[0,1]$. Let $\mu_{i,k}$ denote the mean of $S_{ik}(t)$
w.r.t. the pdf $f(s,\theta_{ik})$. We assume that the parameter vector
$\theta=(\theta_{ij},1\leq i\leq M,1\leq j\leq N)$ is unknown to the players,
i.e., the players have no information about the mean, the distributions or any
other statistics about the rewards from various arms other than what they
observe while playing. We also assume that each player can only observe the
rewards that they get. When there is a collision, we will assume that all
players that choose the arm on which there is a collision get zero reward.
This could be relaxed where the players share the reward in some manner though
the results do not change appreciably.

Let $X_{ij}(t)$ be the reward that player $i$ gets from arm $j$ at time $t$.
Thus, if player $i$ plays arm $k$ at time $t$ (and there is no collision),
$X_{ik}(t)=S_{ik}(t)$, and $X_{ij}(t)=0,j\neq k$. Denote the action of player
$i$ at time $t$ by $a_{i}(t)\in\mathcal{A}:=\\{1,\ldots,N\\}$. Then, the
history seen by player $i$ at time $t$ is
$\mathcal{H}_{i}(t)=\\{(a_{i}(1),X_{i,a_{i}(1)}(1)),\cdots,(a_{i}(t),X_{i,a_{i}(t)}(t))\\}$
with $\mathcal{H}_{i}(0)=\emptyset$. A policy
$\alpha_{i}=(\alpha_{i}(t))_{t=1}^{\infty}$ for player $i$ is a sequence of
maps $\alpha_{i}(t):\mathcal{H}_{i}(t)\to\mathcal{A}$ that specifies the arm
to be played at time $t$ given the history seen by the player. Let
$\mathcal{P}(N)$ be the set of vectors such that

$\displaystyle\mathcal{P}(N):=\\{\mathbf{a}=(a_{1},\ldots,a_{M}):a_{i}\in\mathcal{A},a_{i}\neq
a_{j},\text{for}~{}i\neq j\\}.$

The players have a team objective: namely over a time horizon $T$, they want
to maximize the expected sum of rewards
$\mathbb{E}[\sum_{t=1}^{T}\sum_{i=1}^{M}X_{i,a_{i}(t)}(t)]$ over some time
horizon $T$. If the parameters $\mu_{i,j}$ are known, this could easily be
achieved by picking a bipartite matching

$\mathbf{k}^{**}\in\arg\max_{\mathbf{k}\in\mathcal{P}(N)}\sum_{i=1}^{M}\mu_{i,k_{i}},$
(1)

i.e., the optimal bipartite matching with expected reward from each match.
Note that this may not be unique. Since the expected rewards, $\mu_{i,j}$, are
unknown, the players must pick learning policies that minimize the expected
regret, defined for policies $\alpha=(\alpha_{i},1\leq i\leq M)$ as

$\mathcal{R}_{\alpha}(T)=T\sum_{i}\mu_{i,k_{i}^{**}}-\mathbb{E}_{\alpha}\left[\sum_{t=1}^{T}\sum_{i=1}^{M}X_{i,\alpha_{i}(t)}(t)\right].$
(2)

Our goal is to find a decentralized algorithm that players can use such that
together they minimize the expected regret.

###  II-B Arms with Markovian rewards

Here we follow the model formulation introduced in the previous subsection,
with the exception that the rewards are now considered Markovian. The reward
that player $i$ gets from arm $j$ (when there is no collision) $X_{ij}$, is
modelled as an irreducible, aperiodic, reversible Markov chain on a finite
state space $\mathcal{X}^{i,j}$ and represented by a transition probability
matrix
$P^{i,j}:=\left(p^{i,j}_{x,x^{{}^{\prime}}}:x,x^{{}^{\prime}}\in\mathcal{X}^{i,j}\right)$.
We assume that rewards are bounded and strictly positive, and without loss of
generality lie in $(0,1]$. Let
$\mathbf{\pi}^{i,j}:=\left(\pi^{i,j}_{x},x\in\mathcal{X}^{i,j}\right)$ be the
stationary distribution of the Markov chain $P^{i,j}$. The mean reward from
arm $j$ for player $i$ is defined as
$\mu_{i,j}:=\sum_{x\in\mathcal{X}^{i,j}}x\pi^{i,j}_{x}$. Note that the Markov
chain represented by $P^{i,j}$ makes a state transition only when player $i$
plays arm $j$. Otherwise it remains _rested_.

We note that although we use the ‘big $O$’ notation to emphasis the regret
order, unless otherwise noted results are non-asymptotic.

##  III Some variations on single player multi-armed bandit with i.i.d.
rewards

We first present some variations on the single player non-Bayesian multi-armed
bandit model. These will prove useful later for the multi-player problem
though they should also be of independent interest.

###  III-A ${\tt UCB_{1}}$ with index recomputation every $L$ slots

Consider the classical single player non-Bayesian $N$-armed bandit problem. At
each time $t$, the player picks a particular arm, say $j$, and gets a random
reward $X_{j}(t)$. The rewards $X_{j}(t),1\leq t\leq T$ are independent and
identically distributed according to some unknown probability measure with an
unknown expectation $\mu_{j}$. Without loss of generality, assume that
$\mu_{1}>\mu_{i}>\mu_{N},$ for $i=2,\cdots N-1$. Let $n_{j}(t)$ denote the
number of times arm $j$ has been played by time $t$. Denote
$\Delta_{j}:=\mu_{1}-\mu_{j}$, $\Delta_{min}:=\min_{j,j\neq 1}\Delta_{j}$ and
$\Delta_{max}:=\max_{j}\Delta_{j}$. The regret for any policy $\alpha$ is

$\mathcal{R}_{\alpha}(T):=\mu_{1}T-\sum_{j=1}^{N}\mu_{j}\mathbb{E}_{\alpha}[n_{j}(T)].$
(3)

${\tt UCB_{1}}$ index [4] is defined as

$g_{j}(t):=\overline{X}_{j}(t)+\sqrt{\frac{2\log(t)}{n_{j}(t)}},$ (4)

where $\overline{X}_{j}(t)$ is the average reward obtained by playing arm $j$
by time $t$. It is defined as
$\overline{X}_{j}(t)=\sum_{m=1}^{t}r_{j}(m)/n_{j}(t)$, where $r_{j}(m)$ is the
reward obtained from arm $j$ at time $m$. If the arm $j$ is played at time $t$
then $r_{j}(m)=X_{j}(m)$ and otherwise $r_{j}(t)=0$. Now, an index-based
policy called ${\tt UCB_{1}}$ [4] is to pick the arm that has the highest
index at each instant. It can be shown that this algorithm achieves regret
that grows logarithmically in $T$ non-asymptotically.

An easy variation of the above algorithm which will be useful in our analysis
of subsequent algorithms is the following. Suppose the index is re-computed
only once every $L$ slots. In that case, it is easy to establish the
following.

######  Theorem 1.

Under the ${\tt UCB_{1}}$ algorithm with recomputation of the index once every
$L$ slots, the expected regret by time $T$ is given by

$\mathcal{R}_{\tt UCB_{1}}(T)\leq\sum_{j>1}^{N}\frac{8L\log
T}{\Delta_{j}}+L\left(1+\frac{\pi^{2}}{3}\right)\sum_{j>1}^{N}\Delta_{j}.$ (5)

The proof follows [4] and taking into account the fact that every time a
suboptimal arm is selected, it is played for the next $L$ time slots. We omit
it due to space consideration.

###  III-B ${\tt UCB_{4}}$ Algorithm when index computation is costly

Often, learning algorithms pay a penalty or cost for computation. This is
particularly the case when the algorithms must solve combinatorial
optimization problems that are NP-hard. Such costs also arise in decentralized
settings wherein algorithms pay a communication cost for coordination between
the decentralized players. This is indeed the case, as we shall see later when
we present an algorithm to solve the decentralized multi-armed bandit problem.
Here, however, we will just consider an “abstract” communication or
computation cost. The problem we formulate below can be solved with better
regret bounds than what we present. At this time though we are unable to
design algorithms with better regret bounds, that also help in
decentralization.

Consider a computation cost every time the index is recomputed. Let the cost
be $C$ units. Let $m(t)$ denote the number of times the index is computed by
time $t$. Then, under policy $\alpha$ the expected regret is now given by

$\tilde{\mathcal{R}}_{\alpha}(T):=\mu_{1}T-\sum_{j=1}^{N}\mu_{j}\mathbb{E}_{\alpha}[n_{j}(T)]+C\mathbb{E}_{\alpha}[m(T)].$
(6)

It is easy to argue that the ${\tt UCB_{1}}$ algorithm will give a regret
$\Omega(T)$ for this problem. We present an alternative algorithm called ${\tt
UCB_{4}}$ algorithm, that gives sub-linear regret. Define the ${\tt UCB_{4}}$
index

$g_{j}(t):=\overline{X}_{j}(t)+\sqrt{\frac{3\log(t)}{n_{j}(t)}}.$ (7)

We define an arm $j^{*}(t)$ to be the best arm if $j^{*}(t)\in\arg\max_{1\leq
i\leq N}g_{i}(t).$

Algorithm 1 : $\tt UCB_{4}$

1: Initialization: Select each arm $j$ once for $t\leq N$. Update the $\tt
UCB_{4}$ indices. Set $\eta=1$.

2: while ($t\leq T$) do

3: if ($\eta=2^{p}$ for some $p=0,1,2,\cdots$) then

4: Update the index vector $g(t)$;

5: Compute the best arm $j^{*}(t)$;

6: if $(j^{*}(t)\neq j^{*}(t-1))$ then

7: Reset $\eta=1$;

8: end if

9: else

10: $j^{*}(t)=j^{*}(t-1)$;

11: end if

12: Play arm $j^{*}(t)$;

13: Increment counter $\eta=\eta+1$; $t=t+1$;

14: end while

We will use the following concentration inequality.
Fact 1: Chernoff-Hoeffding inequality [19]
Let $X_{1},\ldots,X_{t}$ be random variables with a common range such that
$\mathbb{E}[X_{t}|X_{1},\ldots,X_{t-1}]=\mu$. Let $S_{t}=\sum_{i=1}^{t}X_{i}$.
Then for all $a\geq 0$,

$\displaystyle\mathbb{P}\left(S_{t}\geq t\mu+a\right)\leq
e^{-2a^{2}/t},~{}~{}\text{and}~{}~{}\mathbb{P}\left(S_{t}\leq
t\mu-a\right)\leq e^{-2a^{2}/t}.$ (8)

######  Theorem 2.

The expected regret for the single player multi-armed bandit problem with per
computation cost $C$ using the ${\tt UCB_{4}}$ algorithm is given by

$\displaystyle\tilde{\mathcal{R}}_{\tt UCB_{4}}(T)$ $\displaystyle\leq$
$\displaystyle(\Delta_{max}+C(1+\log T))\cdot\left(\sum_{j>1}^{N}\frac{12\log
T}{\Delta_{j}^{2}}+2N\right).$

Thus, $\tilde{\mathcal{R}}_{\tt UCB_{4}}(T)=O(\log^{2}T).$

###### Proof.

We prove this in two steps. First, we compute the expected number of times a
suboptimal arm is played and then the expected number of times we recompute
the index.

Consider any suboptimal arm $j>1$. Denote $c_{t,s}=\sqrt{3\log t/s}$ and the
indicator function of the event $A$ by $I\\{A\\}$. let $\tau_{j,m}$ be the
time at which the player makes the $m$th transition to the arm $j$ from
another arm and $\tau_{j,m}^{{}^{\prime}}$ be the time at which the player
makes the $m$th transition from the arm $j$ to another arm. Let
$\tilde{\tau}_{j,m}^{{}^{\prime}}=\min\\{\tau_{j,m}^{{}^{\prime}},T\\}$. Then,
$n_{j}(T)\leq
1+\sum_{m=1}^{T}(\tilde{\tau}_{j,m}^{{}^{\prime}}-\tau_{j,m})I\\{\text{Arm}~{}j~{}\text{is
picked at time}~{}\tau_{j,m},\tau_{j,m}\leq T\\}$

$\displaystyle\leq$ $\displaystyle
1+\sum_{m=1}^{T}(\tilde{\tau}_{j,m}^{{}^{\prime}}-\tau_{j,m})I\\{g_{j}(\tau_{j,m}-1)\geq
g_{1}(\tau_{j,m}-1),\tau_{j,m}\leq T\\}$ $\displaystyle\leq$ $\displaystyle
l+\sum_{m=1}^{T}(\tilde{\tau}_{j,m}^{{}^{\prime}}-\tau_{j,m})I\\{g_{j}(\tau_{j,m}-1)\geq
g_{1}(\tau_{j,m}-1),\tau_{j,m}\leq T,n_{j}(\tau_{j,m}-1)\geq l\\}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
l+\sum_{m=1}^{T}\sum_{p=0}^{\infty}2^{p}I\\{g_{j}(\tau_{j,m}+2^{p}-2)\geq
g_{1}(\tau_{j,m}+2^{p}-2),\tau_{j,m}+2^{p}\leq T,n_{j}(\tau_{j,m}-1)\geq l\\}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle
l+\sum_{m=2}^{T}\sum_{p=0}^{\infty}2^{p}I\\{g_{j}(m+2^{p}-2)\geq
g_{1}(m+2^{p}-2),m+2^{p}\leq T,n_{j}(m-1)\geq l\\}$ $\displaystyle\leq$
$\displaystyle l+\sum_{m=1}^{T}\sum_{p\geq 0,m+2^{p}\leq
T}2^{p}I\\{\overline{X}_{j}(m+2^{p}-1)+c_{m+2^{p}-1,n_{j}(m+2^{p}-1)}\geq$
$\displaystyle\hskip
113.81102pt\overline{X}_{1}(m+2^{p}-1)+c_{m+2^{p}-1,n_{1}(m+2^{p}-1)},n_{j}(m-1)\geq
l\\}$ $\displaystyle\leq$ $\displaystyle l+\sum_{m=1}^{T}\sum_{p\geq
0,m+2^{p}\leq T}2^{p}I\\{\max_{l\leq
s_{j}<m+2^{p}}\overline{X}_{j}(m+2^{p}-1)+c_{m+2^{p}-1,s_{j}}\geq$
$\displaystyle\hskip 113.81102pt\min_{1\leq
s_{1}<m+2^{p}}\overline{X}_{1}(m+2^{p}-1)+c_{m+2^{p}-1,s_{1}}\\}$ (10)
$\displaystyle\leq$ $\displaystyle l+\sum_{m=1}^{\infty}\sum_{p\geq
0,m+2^{p}\leq
T}2^{p}\sum_{s_{1}=1}^{m+2^{p}}\sum_{s_{j}=l}^{m+2^{p}}I\\{\overline{X}_{j}(m+2^{p})+c_{m+2^{p},s_{j}}\geq\overline{X}_{1}(m+2^{p})+c_{m+2^{p},s_{1}}\\}.$

In Algorithm 1 ($\tt UCB_{4}$), if an arm is for the $p$th time consecutively
(without switching to any other arms in between), it is be played for the next
$2^{p}$ slots. Inequality (a) uses this fact. In the inequality (b), we
replace $\tau_{j,m}$ by $m$ which is clearly an upper bound. Now, observe that
the event
$\\{\overline{X}_{j}(m+2^{p})+c_{m+2^{p},s_{j}}\geq\overline{X}_{1}(m+2^{p})+c_{m+2^{p},s_{1}}\\}$
implies at least one of the following events,

$\displaystyle A:=\big{\\{}\overline{X}_{1}(m+2^{p})$ $\displaystyle\leq$
$\displaystyle\mu_{1}-c_{m+2^{p},s_{1}}\big{\\}},\hskip
14.22636ptB:=\big{\\{}\overline{X}_{j}(m+2^{p})\geq\mu_{j}+c_{m+2^{p},s_{j}}\big{\\}},$
(11)
$\displaystyle\text{or}~{}C:=\big{\\{}\mu_{1}<\mu_{j}+2c_{m+2^{p},s_{j}}\big{\\}}.$

Now, using the Chernoff-Hoeffding bound, we get

$\displaystyle\mathbb{P}\left(\overline{X}_{1}(m+2^{p})\leq\mu_{1}-c_{m+2^{p},s_{1}}\right)\leq(m+2^{p})^{-6},~{}\mathbb{P}\left(\overline{X}_{j}(m+2^{p})\geq\mu_{j}+c_{m+2^{p},s_{j}}\right)\leq(m+2^{p})^{-6}.$

For $l=\left\lceil\frac{12\log T}{\Delta^{2}_{j}}\right\rceil$, the last event
in (11) is false. In fact, $\mu_{1}-\mu_{j}-2c_{m+2^{p},s_{j}}$

$\displaystyle=\mu_{1}-\mu_{j}-2\sqrt{3\log(m+2^{p})/s_{j}}$
$\displaystyle\geq\mu_{1}-\mu_{j}-\Delta_{j}=0,~{}\text{for}~{}s_{j}\geq\left\lceil
12\log T/\Delta_{j}^{2}\right\rceil.$ $\displaystyle\text{So, we
get,}~{}\mathbb{E}[n_{j}(T)]\leq\left\lceil 12\log
T/\Delta_{j}^{2}\right\rceil$ $\displaystyle+$
$\displaystyle\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}\sum_{s_{1}=1}^{m+2^{p}}\sum_{s_{j}=1}^{m+2^{p}}2(m+2^{p})^{-6}$
$\displaystyle\leq\left\lceil 12\log T/\Delta_{j}^{2}\right\rceil$
$\displaystyle+$ $\displaystyle
2\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}(m+2^{p})^{-4}\leq\frac{12\log
T}{\Delta^{2}_{j}}+2.$ (12)

Next, we upper-bound the expectation of $m(T)$, the number of index
computations performed by time $T$. We can write $m(T)=m_{1}(T)+m_{2}(T)$,
where $m_{1}(T)$ is the number of index updates that result in an optimal
allocation, and $m_{2}(T)$ is the number of index updates that result in a
suboptimal allocation. Clearly, the number of updates resulting in a
suboptimal allocation is less than the number of times a suboptimal arm is
played. Thus,

$\mathbb{E}[m_{2}(T)]\leq\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)].$ (13)

To bound $\mathbb{E}[m_{1}(T)]$, let $\tau_{l}$ be the time at which the
player makes the $l$th transition to an optimal arm from a suboptimal arm and
$\tau_{l}^{\prime}$ be the time at which the player makes the $l$th transition
from an optimal arm to a suboptimal arm. Then,
$m_{1}(T)\leq\sum_{l=1}^{n_{sub}(T)}\log|\tau_{l}-\tau_{l}^{\prime}|$, where
$n_{sub}(T)$ is the total number of such transitions by time $T$. Clearly,
$n_{sub}(T)$ is upper-bounded by the total number of times the player picks a
sub-optimal arm. Also, $\log|\tau_{l}-\tau_{l}^{\prime}|\leq\log T$. So,

$\mathbb{E}[m_{1}(T)]\leq\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]\cdot\log T.$ (14)

Thus, from bounds (13) and (14), we get

$\mathbb{E}[m(T)]\leq\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]\cdot(1+\log T).$ (15)

Now, using equation (6), the expected regret is

$\displaystyle\tilde{\mathcal{R}}_{\tt UCB_{4}}(T)$ $\displaystyle=$
$\displaystyle\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]\cdot\Delta_{j}+C\mathbb{E}[m(T)]\leq\Delta_{max}\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]+C\mathbb{E}[m(T)]$
$\displaystyle\leq$ $\displaystyle\left(\Delta_{max}+C(1+\log
T)\right)\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)].$

by using (15). Now, by bound (12), we get the desired bound on the expected
regret. ∎

Remarks. 1\. It is easy to show that the lower bound for the single player MAB
problem with computation costs is $\Omega(\log T)$. This can be achieved by
the ${\tt UCB_{2}}$ algorithm [4]. To see this, note that the number of times
the player selects a suboptimal arm when using ${\tt UCB_{2}}$ is $O(\log T)$.
Since $\mathbb{E}[n_{j}(T)]=O(\log T)$, we get
$\mathbb{E}[\sum_{j>1}^{N}n_{j}(T)]=O(\log T),$ and also
$\mathbb{E}[m_{2}(T)]=O(\log T).$ Now, since the epochs are not getting reset
after every switch and are exponentially spaced, the number of updates that
result in the optimal allocation, $m_{1}(T)\leq\log T.$ These together yield

$\tilde{\mathcal{R}}_{\tt
UCB_{2}}(T)\leq\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]\cdot\Delta_{j}+C\mathbb{E}[m(T)]=O(\log
T).$

2\. Variations of the ${\tt UCB_{2}}$ algorithm that use a deterministic
schedule can also be used [20]. But it is unknown at this time if these can be
used in solving the decentralized MAB problem that we introduce in the next
section. This is the main reason for introducing the ${\tt UCB_{4}}$
algorithm.

###  III-C Algorithms with finite precision indices

Often, there might be a cost to compute the indices to a particular precision.
In that case, indices may be known upto some $\epsilon$ precision, and it may
not possible to tell which of two indices is greater if they are within
$\epsilon$ of each other. The question then is how is the performance of
various index-based policies such as ${\tt UCB_{1},UCB_{4}}$, etc. affected if
there are limits on index resolution, and only an arm with an
$\epsilon$-highest index can be picked. We first show that if $\Delta_{min}$
is known, we can fix a precision $0<\epsilon<\Delta_{min}$, so that ${\tt
UCB_{4}}$ algorithm will achieve order log-squared regret growth with $T$. If
$\Delta_{min}$ is not known, we can pick a positive monotone sequence
$\\{\epsilon_{t}\\}$ such that $\epsilon_{t}\to 0$, as $t\to\infty$. Denote
the cost of computation for $\epsilon$-precision be $C(\epsilon)$. We assume
that $C(\epsilon)\rightarrow\infty$ monotonically as $\epsilon\rightarrow 0$.

######  Theorem 3.

(i) If $\Delta_{min}$ is known, choose an $0<\epsilon<\Delta_{min}$. Then, the
expected regret of the ${\tt UCB_{4}}$ algorithm with $\epsilon$-precise
computations is given by

$\displaystyle\tilde{\mathcal{R}}_{\tt UCB_{4}}(T)$ $\displaystyle\leq$
$\displaystyle\left(\Delta_{max}+C(\epsilon)(1+\log
T)\right)\cdot\left(\sum_{j>1}^{N}\frac{12\log
T}{(\Delta_{j}-\epsilon)^{2}}+2N\right).$

Thus, $\tilde{\mathcal{R}}_{\tt UCB_{4}}(T)=O(\log^{2}T).$
(ii) If $\Delta_{min}$ is unknown, denote $\epsilon_{min}=\Delta_{min}/2$ and
choose a positive monotone sequence $\\{\epsilon_{t}\\}$ such that
$\epsilon_{t}\to 0$ as $t\to\infty$. Then, there exists a $t_{0}>0$ such that
for all $T>t_{0}$,

$\displaystyle\tilde{\mathcal{R}}_{\tt UCB_{4}}(T)$ $\displaystyle\leq$
$\displaystyle\left(\Delta_{max}+C(\epsilon_{min})\right)t_{0}+(\Delta_{max}+C(\epsilon_{T})(1+\log
T))\cdot\left(\sum_{j>1}^{N}\frac{12\log
T}{(\Delta_{j}-\epsilon_{min})^{2}}+2N\right)$

where $t_{0}$ is the smallest $t$ such that $\epsilon_{t_{0}}<\epsilon_{min}$.
Thus by choosing an arbitrarily slowly increasing sequence
$\\{\epsilon_{t}\\}$, we can make the regret arbitrarily close to
$O(\log^{2}T)$ asymptotically.

###### Proof.

(i) The proof is only a slight modification of the proof given in Theorem 2.
Due to the $\epsilon$ precision, the player will pick a suboptimal arm if the
event
$\\{\overline{X}_{j}(m+2^{p})+c_{m+2^{p},s_{j}}+\epsilon\geq\overline{X}_{1}(m+2^{p})+c_{m+2^{p},s_{1}}\\}$
occurs. Thus equation (III-B) becomes, $n_{j}(T)$

$\leq l+\sum_{m=1}^{\infty}\sum_{p\geq 0,m+2^{p}\leq
T}2^{p}\sum_{s_{1}=1}^{m+2^{p}}\sum_{s_{j}=l}^{m+2^{p}}I\\{\overline{X}_{j}(m+2^{p})+c_{m+2^{p},s_{j}}+\epsilon\geq\overline{X}_{1}(m+2^{p})+c_{m+2^{p},s_{1}}\\}.$

Now, the event
$\\{\overline{X}_{j}(m+2^{p})+c_{m+2^{p},s_{j}}+\epsilon\geq\overline{X}_{1}(m+2^{p})+c_{m+2^{p},s_{1}}\\}$
implies that at least one of the following events must occur:

$\displaystyle
A:=\big{\\{}\overline{X}_{1}(m+2^{p})\leq\mu_{1}-c_{m+2^{p},s_{1}}\big{\\}},$
$\displaystyle
B:=\big{\\{}\overline{X}_{j}(m+2^{p})\geq\mu_{j}+\epsilon+c_{m+2^{p},s_{j}}\big{\\}},$
$\displaystyle
C:=\big{\\{}\mu_{1}<\mu_{j}+\epsilon+2c_{m+2^{p},s_{j}}\big{\\}},$
$\displaystyle\text{or}~{}D:=\big{\\{}\mu_{1}<\mu_{j}+\epsilon\big{\\}}.$ (16)

Since
$\\{\overline{X}_{j}(m+2^{p})\geq\mu_{j}+\epsilon+c_{m+2^{p},s_{j}}\\}\subseteq\\{\overline{X}_{j}(m+2^{p})\geq\mu_{j}+c_{m+2^{p},s_{j}}\\}$,
we have

$\displaystyle\mathbb{P}(\\{\overline{X}_{j}(m+2^{p})$ $\displaystyle\geq$
$\displaystyle\mu_{j}+\epsilon+c_{m+2^{p},s_{j}}\\})\leq\mathbb{P}(\\{\overline{X}_{j}(m+2^{p})\geq\mu_{j}+c_{m+2^{p},s_{j}}\\}).$

Also, for $l=\left\lceil 12\log T/(\Delta_{j}-\epsilon)^{2}\right\rceil$, the
event $C$ cannot happen. In fact,
$\mu_{1}-\mu_{j}-\epsilon-2c_{t+2^{p},s_{j}}=\mu_{1}-\mu_{j}-\epsilon-2\sqrt{\frac{3\log(t+2^{p})}{s_{j}}}\geq\mu_{1}-\mu_{j}-\epsilon-(\Delta_{j}-\epsilon)=0,$
for $s_{j}\geq\left\lceil 12\log T/(\Delta_{j}-\epsilon)^{2}\right\rceil$. If
$\epsilon<\Delta_{min}$, the last event (D) in equation (III-C) is also not
true. Thus, for $0<\epsilon<\Delta_{min}$, we get

$\mathbb{E}[n_{j}(T)]\leq\frac{12\log(n)}{(\Delta_{j}-\epsilon)^{2}}+2.$ (17)

The rest of the proof is the same as in Theorem 2. Now, if $\Delta_{min}$ is
known, we can choose $0<\epsilon<\Delta_{min}$ and by Theorem 2 and bound
(17), we get the desired result.

(ii) If $\Delta_{min}$ is unknown, we can choose a positive monotone sequence
$\\{\epsilon_{t}\\}$ such that $\epsilon_{t}\to 0$ as $t\to\infty$. Thus,
there exists a $t_{0}$ such that for $t>t_{0}$, $\epsilon_{t}<\epsilon_{min}$.
We may get a linear regret upto time $t_{0}$ but after that the analysis
follows that in the proof of Theorem 2, and regret grows only sub-linearly.
Since $C(\cdot)$ is monotone, $C(\epsilon_{T})>C(\epsilon_{t})$ for all $t<T$.
The last part can now be trivially established using the obtained bound on the
expected regret. ∎

##  IV Single Player Multi-armed Bandit with Markovian Rewards

Now, we consider the scenario where the rewards obtained from an arm are not
i.i.d. but come from a Markov chain. Reward from each arm is modelled as an
irreducible, aperiodic, reversible Markov chain on a finite state space
$\mathcal{X}^{i}$ and represented by a transition probability matrix
$P^{i}:=\left(p^{i}_{x,x^{{}^{\prime}}}:x,x^{{}^{\prime}}\in\mathcal{X}^{i}\right)$.
Assume that the reward space $\mathcal{X}^{i}\subseteq(0,1]$. Let
$X_{i}(1),X_{i}(2),\ldots$ denote the successive rewards from arm $i$. All
arms are mutually independent. Let
$\mathbf{\pi^{i}}:=\left(\pi^{i}_{x},x\in\mathcal{X}^{i}\right)$ be the
stationary distribution of the Markov chain $P^{i}$. Since the Markov chains
are ergodic under these assumptions, the mean reward from arm $i$ is given by
$\mu_{i}:=\sum_{x\in\mathcal{X}^{i}}x\pi^{i}_{x}$. Without loss of generality,
assume that $\mu_{1}>\mu_{i}>\mu_{N},$ for $i=2,\cdots N-1$. As before,
$n_{j}(t)$ denotes the number of times arm $j$ has been played by time $t$.
Denote $\Delta_{j}:=\mu_{1}-\mu_{j}$, $\Delta_{min}:=\min_{j,j\neq
1}\Delta_{j}$ and $\Delta_{max}:=\max_{j}\Delta_{j}$. Denote
$\pi_{min}:=\min_{1\leq i\leq N,x\in\mathcal{X}^{i}}\pi^{i}_{x}$,
$x_{max}:=\max_{1\leq i\leq N,x\in\mathcal{X}^{i}}x$ and $x_{min}:=\min_{1\leq
i\leq N,x\in\mathcal{X}^{i}}x$. Let
${\hat{\pi}^{i}}_{x}:=\max\\{\pi^{i}_{x},1-\pi^{i}_{x}\\}$ and
$\hat{\pi}_{max}:=\max_{1\leq i\leq
N,x\in\mathcal{X}^{i}}{\hat{\pi}^{i}}_{x}$. Let $|\mathcal{X}^{i}|$ denote the
cardinality of the state space $\mathcal{X}^{i}$,
$|\mathcal{X}|_{max}:=\max_{1\leq i\leq N}|\mathcal{X}^{i}|$. Let $\rho^{i}$
be the eigenvalue gap, $1-\lambda_{2}$, where $\lambda_{2}$ is the second
largest eigenvalue of the matrix ${P^{i}}^{2}$. Denote
$\rho_{max}:=\max_{1\leq i\leq N}\rho^{i}$ and $\rho_{min}:=\min_{1\leq i\leq
N}\rho^{i}$, where $\rho^{i}$ is the eigenvalue gap of the $i$th arm.

The total reward obtained by the time $T$ is then given by
$S_{T}=\sum_{j=1}^{N}\sum_{s=1}^{n_{j}(T)}X_{j}(s)$. The regret for any policy
$\alpha$ is defined as

$\tilde{\mathcal{R}}_{M,\alpha}(T):=\mu_{1}T-\mathbb{E}_{\alpha}\sum_{j=1}^{N}\sum_{s=1}^{n_{j}(T)}X_{j}(s)+C\mathbb{E}_{\alpha}[m(T)]$
(18)

where $C$ is the cost per computation and $m(T)$ is the number of times the
index is computed by time $T$, as described in section III. Define the index

$g_{j}(t):=\overline{X}_{j}(t)+\sqrt{\frac{\kappa\log(t)}{n_{j}(t)}},$ (19)

where $\overline{X}_{j}(t)$ is the average reward obtained by playing arm $j$
by time $t$, as defined in the previous section. $\kappa$ can be any constant
satisfying $\kappa>168|\mathcal{X}|_{max}^{2}/\rho_{min}$.

We introduce one more notation here. If $\mathcal{F}$ and $\mathcal{G}$ are
two $\sigma$-algebras, then $\mathcal{F}\vee\mathcal{G}$ denotes the smallest
$\sigma$-algebra containing $\mathcal{F}$ and $\mathcal{G}$. Similarly, if
$\\{\mathcal{F}_{t},t=1,2,\ldots\\}$ is a collection of $\sigma$-algebras,
then $\vee_{t\geq 1}F_{t}$ denotes the smallest $\sigma-$algebra containing
$\mathcal{F}_{1},\mathcal{F}_{2},\ldots$

The following can be derived easily from Lemma 4 [5], reproduced in the
appendix.

######  Lemma 1.

If the reward of each arm is given by a Markov chain satisfying the hypothesis
of Lemma 4, then under any policy $\alpha$ we have

$\tilde{\mathcal{R}}_{M,\alpha}(T)\leq\sum_{j=2}^{N}\Delta_{j}\mathbb{E}_{\alpha}[n_{j}(T)]+K_{\mathcal{X},P}+C\mathbb{E}_{\alpha}[m(T)]$
(20)

where
$K_{\mathcal{X},P}=\sum_{j=1}^{N}\sum_{x\in\mathcal{X}^{j}}x/\pi^{j}_{min}$
and $\pi^{j}_{min}=\min_{x\in\mathcal{X}^{j}}\pi^{j}_{x}$

###### Proof.

Let $X_{j}(1),X_{j}(2),\ldots$ denote the successive rewards from arm $j$. Let
$\mathcal{F}^{j}_{t}$ denotes the $\sigma$-algebra generated by
$\left(X_{j}(1),\ldots,X_{j}(t)\right)$. Let $\mathcal{F}^{j}=\vee_{t\geq
1}\mathcal{F}^{j}_{t}$ and $\mathcal{G}^{j}=\vee_{i\neq j}F^{i}$. Since arms
are independent, $\mathcal{G}^{j}$ is independent of $\mathcal{F}^{j}$.
Clearly, $n_{j}(T)$ is a stopping time with respect to
$\mathcal{G}^{j}\vee\mathcal{F}^{j}_{T}$. The total reward is
$S_{T}=\sum_{j=1}^{N}\sum_{s=1}^{n_{j}(T)}X_{j}(s)=\sum_{j=1}^{N}\sum_{x\in\mathcal{X}^{j}}xN(x,n_{j}(T))$
where $N(x,n_{j}(T)):=\sum_{t=1}^{n_{j}(T)}I\\{X_{j}(t)=x\\}$. Taking the
expectation and using the Lemma 4, we have
$\left\lvert\mathbb{E}[S_{T}]-\sum_{j=1}^{N}\sum_{x\in\mathcal{X}^{j}}x\pi^{j}_{x}\mathbb{E}[n_{j}(T)]\right\rvert\leq\sum_{j=1}^{N}\sum_{x\in\mathcal{X}^{j}}x/\pi^{j}_{min}$,
which implies
$\left\lvert\mathbb{E}[S_{T}]-\sum_{j=1}^{N}\mu_{j}\mathbb{E}[n_{j}(T)]\right\rvert\leq
K_{\mathcal{X},P},$ where
$K_{\mathcal{X},P}=\sum_{j=1}^{N}\sum_{x\in\mathcal{X}^{j}}x/\pi^{j}_{min}$.
Since regret
$\tilde{\mathcal{R}}_{M,\alpha}(T)=\mu_{1}T-\mathbb{E}_{\alpha}\sum_{j=1}^{N}\sum_{t=1}^{n_{j}(T)}X_{j}(t)+C\mathbb{E}_{\alpha}[m(T)]$
(c.f. equation (18)), we get

$|\tilde{\mathcal{R}}_{M,\alpha}(T)-\left(\mu_{1}T-\sum_{j=1}^{N}\mu_{j}\mathbb{E}[n_{j}(T)]+C\mathbb{E}_{\alpha}[m(T)]\right)|\leq
K_{\mathcal{X},P}.$

∎

We will use a concentration inequality for Markov chains (Lemma 5, from [21]),
reproduced in the appendix.

######  Theorem 4.

(i) If $|\mathcal{X}|_{max}$ and $\rho_{min}$ are known, choose
$\kappa>168|\mathcal{X}|_{max}^{2}/\rho_{min}$. Then, the expected regret
using the ${\tt UCB_{4}}$ algorithm with the index defined as in (19) for the
single player multi-armed bandit problem with Markovian rewards and per
computation cost $C$ is given by

$\displaystyle\tilde{\mathcal{R}}_{M,\tt UCB_{4}}(T)$ $\displaystyle\leq$
$\displaystyle(\Delta_{max}+C(1+\log
T))\cdot\left(\sum_{j>1}^{N}\frac{4\kappa\log
T}{\Delta_{j}^{2}}+N(2D+1)\right)+K_{\mathcal{X},P}$

where $D=\frac{|\mathcal{X}|_{max}}{\pi_{min}}$. Thus,
$\tilde{\mathcal{R}}_{M,\tt UCB_{4}}(T)=O(\log^{2}T).$
(ii) If $|\mathcal{X}|_{max}$ and $\rho_{min}$ are not known, choose a
positive monotone sequence $\\{\kappa_{t}\\}$ such that
$\kappa_{t}\rightarrow\infty$ as $t\rightarrow\infty$ and $\kappa_{t}\leq t$.
Then, $\tilde{\mathcal{R}}_{M,\tt UCB_{4}}(T)=O(\kappa_{T}\log^{2}T)$. Thus,
by choosing an arbitrarily slowly increasing sequence $\\{\kappa_{t}\\}$ we
can make the regret arbitrarily close to $\log^{2}T$.

###### Proof.

(i) Consider any suboptimal arm $j>1$. Denote $c_{t,s}=\sqrt{\kappa\log t/s}$.
As in the proof of Theorem 2, we start by bounding $n_{j}(T)$. The initial
steps are the same as in the proof of Theorem 2. So, we skip those steps and
start from the inequality (III-B) there.

$\displaystyle n_{j}(T)$ $\displaystyle\leq$ $\displaystyle
l+\sum_{m=1}^{\infty}\sum_{p\geq 0,m+2^{p}\leq
T}2^{p}\sum_{s_{1}=1}^{m+2^{p}}\sum_{s_{j}=l}^{m+2^{p}}I\\{\overline{X}_{j}(m+2^{p})+c_{m+2^{p},s_{j}}\geq\overline{X}_{1}(m+2^{p})+c_{m+2^{p},s_{1}}\\}.$

The event
$\\{\overline{X}_{j}(m+2^{p})+c_{m+2^{p},s_{j}}\geq\overline{X}_{1}(m+2^{p})+c_{m+2^{p},s_{1}}\\}$
is true only if at least one of the events shown in display (11) are true. We
note that, for any initial distribution $\lambda^{j}$ for arm $j$,

$N_{\lambda^{j}}=\left\lVert\left(\frac{\lambda^{j}_{x}}{\pi^{j}_{x}},x\in\mathcal{X}^{j}\right)\right\rVert_{2}\leq\sum_{x\in\mathcal{X}^{j}}\left\lVert\left(\frac{\lambda^{j}_{x}}{\pi^{j}_{x}}\right)\right\rVert_{2}\leq\frac{1}{\pi_{min}}.$
(21)

Also, $x_{max}\leq 1$. Let $n^{j}_{x}(s_{j})$ be the number of times the state
$x$ is observed when arm $j$ is pulled $s_{j}$ times. Then, the probability of
the first event in (11),
$\mathbb{P}(\overline{X}_{j}(m+2^{p})\geq\mu_{j}+c_{m+2^{p},s_{j}})$

$\displaystyle=\mathbb{P}\left(\sum_{x\in\mathcal{X}^{j}}xn^{j}_{x}(s_{j})\geq
s_{j}\sum_{x\in\mathcal{X}^{j}}x\pi^{j}_{x}+s_{j}c_{m+2^{p},s_{j}}\right)=\mathbb{P}\left(\sum_{x\in\mathcal{X}^{j}}(n^{j}_{x}(s_{j})-s_{j}\pi^{j}_{x})\geq
s_{j}c_{m+2^{p},s_{j}}/x\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{x\in\mathcal{X}^{j}}\mathbb{P}\left(n^{j}_{x}(s_{j})-s_{j}\pi^{j}_{x}\geq\frac{s_{j}c_{m+2^{p}}}{x|\mathcal{X}^{j}|}\right)=\sum_{x\in\mathcal{X}^{j}}\mathbb{P}\left(\frac{\sum_{t=1}^{s_{j}}I\\{X_{j}(t)=x\\}-s_{j}\pi^{j}_{x}}{s_{j}{\hat{\pi}^{j}}_{x}}\geq\frac{c_{m+2^{p},s_{j}}}{x|\mathcal{X}^{j}|\hat{\pi}^{j}_{x}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{x\in\mathcal{X}^{j}}N_{\lambda^{j}}(m+2^{p})^{-\kappa\rho^{i}/28x^{2}|\mathcal{X}^{j}|^{2}(\hat{\pi}^{j}_{x})^{2}}~{}~{}~{}\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{|\mathcal{X}|_{max}}{\pi_{min}}(m+2^{p})^{-\kappa\rho_{min}/28|\mathcal{X}|_{max}^{2}}.$

The inequality (a) follows after some simple algebra, which we skip due to
space limitations. The inequality (b) follows by defining the function
$f(X_{j}(t))=(I\\{X_{j}(t)=x\\}-\pi^{j}_{x})/{\hat{\pi}^{j}}_{x}$ and using
the Lemma 5. For inequality (c) we used the facts that $N_{\lambda^{j}}\leq
1/\pi_{min}$, $x_{max}\leq 1$ and ${\hat{\pi}_{max}}\leq 1$. Thus,

$\mathbb{P}(\overline{X}_{j}(m+2^{p})\geq\mu_{j}+c_{m+2^{p},s_{j}})\leq
D(m+2^{p})^{-\kappa\rho_{min}/28|\mathcal{X}|_{max}|^{2}}$ (22)

where $D=\frac{|\mathcal{X}|_{max}}{\pi_{min}}$. Similarly we can get,

$\mathbb{P}(\overline{X}_{1}(m+2^{p})\leq\mu_{1}-c_{m+2^{p},s_{1}})\leq
D(m+2^{p})^{-\kappa\rho_{min}/28|\mathcal{X}|_{max}|^{2}}$ (23)

For $l=\left\lceil 4\kappa\log T/\Delta^{2}_{j}\right\rceil$, the last event
in (11) is false. In fact, $\mu_{1}-\mu_{j}-2c_{m+2^{p},s_{j}}$

$\displaystyle=\mu_{1}-\mu_{j}-2\sqrt{\kappa\log(m+2^{p})/s_{j}}\geq\mu_{1}-\mu_{j}-\Delta_{j}=0,~{}\text{for}~{}s_{j}\geq\left\lceil
4\kappa\log T/\Delta^{2}_{j}\right\rceil.~{}\text{Thus},$
$\displaystyle\mathbb{E}[n_{j}(T)]$ $\displaystyle\leq$
$\displaystyle\left\lceil\frac{4\kappa\log
T}{\Delta_{j}^{2}}\right\rceil+\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}\sum_{s_{1}=1}^{m+2^{p}}\sum_{s_{j}=1}^{m+2^{p}}2D(m+2^{p})^{-\frac{\kappa\rho_{min}}{28|\mathcal{X}|_{max}|^{2}}}$
$\displaystyle=\left\lceil\frac{4\kappa\log
T}{\Delta_{j}^{2}}\right\rceil+2D\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}(m+2^{p})^{-\frac{\kappa\rho_{min}-56|\mathcal{X}|_{max}^{2}}{28|\mathcal{X}|_{max}^{2}}}.$
(24)

When $\kappa>168|\mathcal{X}|_{max}^{2}/\rho_{min}$, the above summation
converges to a value less that $1$ and we get

$\mathbb{E}[n_{j}(T)]\leq\frac{4\kappa\log T}{\Delta^{2}_{j}}+(2D+1).$ (25)

Now, from the proof of Theorem 2 (equation (15)),

$\mathbb{E}[m(T)]\leq\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]\cdot(1+\log T).$ (26)

Now, using inequality (20), the expected regret $\tilde{\mathcal{R}}_{M,\tt
UCB_{4}}(T)=$

$\displaystyle=$
$\displaystyle\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]\cdot\Delta_{j}+C\mathbb{E}[m(T)]+K_{\mathcal{X},P}\leq\Delta_{max}\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]+C\mathbb{E}[m(T)]+K_{\mathcal{X},P}$
$\displaystyle\leq$ $\displaystyle\left(\Delta_{max}+C(1+\log
T)\right)\sum_{j>1}^{N}\mathbb{E}[n_{j}(T)]+K_{\mathcal{X},P}.$

by using (26). Now, by bound (25), we get the desired bound on the expected
regret.
(ii) Replacing $\kappa$ with $\kappa_{t}$, equation (IV) becomes

$\displaystyle\mathbb{E}[n_{j}(T)]$ $\displaystyle\leq$
$\displaystyle\left\lceil\frac{4\kappa_{T}\log
T}{\Delta_{j}^{2}}\right\rceil+2D\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}(m+2^{p})^{-\frac{\kappa_{m+2^{p}}\rho_{min}-56|\mathcal{X}|_{max}^{2}}{28|\mathcal{X}|_{max}^{2}}}$

Since, $\kappa_{t}\rightarrow\infty$ as $t\rightarrow\infty$, the exponent
${-\frac{\kappa_{m+2^{p}}\rho_{min}-56|\mathcal{X}|_{max}^{2}}{28|\mathcal{X}|_{max}^{2}}}$
becomes smaller that $-4$ for sufficiently large $m$ and $p$, and the above
summation converges, yielding the desired result. ∎

We note that we have used the results in [22] in the above proof. We note that
the results for Markovian reward just presented extend easily even with finite
precision indices. As before, suppose the cost of computation for
$\epsilon$-precision is $C(\epsilon)$. We assume that
$C(\epsilon)\rightarrow\infty$ monotonically as $\epsilon\rightarrow 0$. We
formally state the following result, which we will use in section VI.

######  Theorem 5.

(i) If $\Delta_{min}$, $|\mathcal{X}|_{max}$ and $\rho_{min}$ are known,
choose an $0<\epsilon<\Delta_{min}$, and a
$\kappa>168|\mathcal{X}|_{max}^{2}/\rho_{min}$. Then, the expected regret
using the ${\tt UCB_{4}}$ algorithm with the index defined as in (19) for the
single player multi-armed bandit problem with Markovian rewards with
$\epsilon$-precise computations is given by

$\displaystyle\tilde{\mathcal{R}}_{M,\tt UCB_{4}}(T)$ $\displaystyle\leq$
$\displaystyle\left(\Delta_{max}+C(\epsilon)(1+\log
T)\right)\cdot\left(\sum_{j>1}^{N}\frac{4\kappa\log
T}{(\Delta_{j}-\epsilon)^{2}}+N(2D+1)\right).$

where $D=\frac{|\mathcal{X}|_{max}}{\pi_{min}}$. Thus,
$\tilde{\mathcal{R}}_{M,\tt UCB_{4}}(T)=O(\log^{2}T).$
(ii) If $\Delta_{min}$, $|\mathcal{X}|_{max}$ and $\rho_{min}$ are unknown,
choose a positive monotone sequences $\\{\epsilon_{t}\\}$ such that and
$\\{\kappa_{t}\\}$ such that $\kappa_{t}\leq t$, $\epsilon_{t}\to 0$ and
$\kappa_{t}\rightarrow\infty$ as $t\to\infty$. Then,
$\tilde{\mathcal{R}}_{M,\tt
UCB_{4}}(T)=O(C(\epsilon_{T})\kappa_{T}\log^{2}T)$. We can choose
$\\{\epsilon_{t}\\}$ and $\\{\kappa_{t}\\}$ as two arbitrarily slowly
increasing sequences and thus the regret can be made arbitrarily close to
$\log^{2}(T)$.

The proof follows by a combination of the proof of the theorems 3 and 4, and
is omitted.

##  V The Decentralized MAB problem with i.i.d. rewards

We now consider the decentralized multi-armed bandit problem with i.i.d.
rewards wherein multiple players play at the same time. Players have no
information about means or distribution of rewards from various arms. There
are no dedicated control channels for coordination or communication between
the players. If two or more players pick the same arm, we assume that neither
gets any reward. Tshis is an online learning problem of distributed bipartite
matching.

Distributed algorithms for bipartite matching algorithms are known [23, 24]
which determine an $\epsilon$-optimal matching with a ‘minimum’ amount of
information exchange and computation. However, every run of this distributed
bipartite matching algorithm incurs a cost due to computation, and
communication necessary to exchange some information for decentralization. Let
$C$ be the cost per run, and $m(t)$ denote the number of times the distributed
bipartite matching algorithm is run by time t. Then, under policy $\alpha$ the
expected regret is

$\mathcal{R}_{\alpha}(T)=T\sum_{i=1}^{M}\mu_{i,k_{i}^{**}}-\mathbb{E}_{\alpha}\left[\sum_{t=1}^{T}\sum_{i=1}^{M}X_{i,\alpha_{i}(t)}(t)\right]+C\mathbb{E}[m(T)].$
(27)

where $\mathbf{k}^{**}$ is the optimal matching as defined in equation (1) in
section II-A.
Temporal Structure. We divide time into frames. Each frame is one of two
kinds: a decision frame, and an exploitation frame. In the decision frame, the
index is recomputed, and the distributed bipartite matching algorithm run
again to determine the new matching. The length of such a frame can be seen as
cost of the algorithm. We further divide the decision frame into two phases, a
negotiation phase and an interrupt phase (see Figure 1). The information
exchange needed to compute an $\epsilon$-optimal matching is done in the
negotiation phase. In the interrupt phase, a player signals to other players
if his allocation has changed. In the exploitation frame, the current matching
is exploited without updating the indices. Later, we will allow the frame
lengths to increase with time.

We now present the ${\tt dUCB_{4}}$ algorithm, a decentralized version of
${\tt UCB_{4}}$. For each player $i$ and each arm $j$, we define a ${\tt
dUCB_{4}}$ index at the end of frame $t$ as

$g_{i,j}(t):=\overline{X}_{i,j}(t)+\sqrt{\frac{(M+2)\log
n_{i}(t)}{n_{i,j}(t)}},$ (28)

where $n_{i}(t)$ is the number of successful plays (without collisions) of
player $i$ by frame $t$, $n_{i,j}(t)$ is the number of times player $i$ picks
arm $j$ successfully by frame $t$. $\overline{X}_{i,j}(t)$ is the sample mean
of rewards from arm $j$ for player $i$ from $n_{i,j}(t)$ samples. Let $g(t)$
denote the vector $(g_{i,j}(t),1\leq i\leq M,1\leq j\leq N)$. Note that $g$ is
computed only in the decision frames using the information available upto that
time. Each player now uses the ${\tt dUCB_{4}}$ algorithm. We will refer to an
$\epsilon$-optimal distributed bipartite matching algorithm as ${\tt
dBM_{\epsilon}}(g(t))$ that yields a solution
$\mathbf{k}^{*}(t):=(k_{1}^{*}(t),\ldots,k_{M}^{*}(t))\in\mathcal{P}(N)$ such
that
$\sum_{i=1}^{M}g_{i,k^{*}_{i}(t)}(t)\geq\sum_{i=1}^{M}g_{i,k_{i}}(t))-\epsilon,~{}\forall\mathbf{k}\in\mathcal{P}(N),\mathbf{k}\neq\mathbf{k}^{*}$.
Let $\mathbf{k}^{**}\in\mathcal{P}(N)$ be such that
$\mathbf{k}^{**}\in\arg\max_{\mathbf{k}\in\mathcal{P}(N)}\sum_{i=1}^{M}\mu_{i,\mathbf{k}_{i}},$
i.e., an optimal bipartite matching with expected rewards from each matching.
Denote $\mu^{**}:=\sum_{i=1}^{M}\mu_{i,\mathbf{k}_{i}^{**}}$, and define
$\Delta_{\mathbf{k}}:=\mu^{**}-\sum_{i=1}^{M}\mu_{i,\mathbf{k}_{i}},~{}\mathbf{k}\in\mathcal{P}(N)$.
Let
$\Delta_{min}=\min_{\mathbf{k}\in\mathcal{P}(N),\mathbf{k}\neq\mathbf{k}^{**}}\Delta_{\mathbf{k}}$
and $\Delta_{max}=\max_{\mathbf{k}\in\mathcal{P}(N)}\Delta_{\mathbf{k}}$. We
assume that $\Delta_{min}>0$.

Algorithm 2 $\tt dUCB_{4}$ for User $i$

1: Initialization: Play a set of matchings so that each player plays each arm
at least once. Set counter $\eta=1$.

2: while ($t\leq T$) do

3: if ($\eta=2^{p}~{}\text{for some}~{}p=0,1,2,\cdots$) then

4: //Decision frame:

5: Update $g(t)$;

6: Participate in the ${\tt dBM_{\epsilon}}(g(t))$ algorithm to obtain a match
$k_{i}^{*}(t)$;

7: if $(k_{i}^{*}(t)\neq k_{i}^{*}(t-1))$ then

8: Use interrupt phase to signal an INTERRUPT to all other players about
changed allocation;

9: Reset $\eta=1$;

10: end if

11: if (Received an INTERRUPT) then

12: Reset $\eta=1$;

13: end if

14: else

15: // Exploitation frame:

16: $k_{i}^{*}(t)=k_{i}^{*}(t-1)$;

17: end if

18: Play arm $k_{i}^{*}(t)$;

19: Increment counter $\eta=\eta+1$, $t=t+1$;

20: end while

In the $\tt dUCB_{4}$ algorithm, at the end of every decision frame, the ${\tt
dBM_{\epsilon}}(g(t))$ will give a legitimate matching with no two players
colliding on any arm. Thus, the regret accrues either if the matching
$\mathbf{k}(t)$ is not the optimal matching $\mathbf{k}^{**}$, or if a
decision frame is employed by the players to recompute the matching. Every
time a frame is a decision frame, it adds a cost $C$ to the regret. The cost
$C$ depends on two parameters: (a) the precision of the bipartite matching
algorithm $\epsilon_{1}>0$, and (b) the precision of the index representation
$\epsilon_{2}>0$. A bipartite matching algorithm has an
$\epsilon_{1}$-precision if it gives an $\epsilon_{1}$-optimal matching. This
would happen, for example, when such an algorithm is run only for a finite
number of rounds. The index has an $\epsilon_{2}$-precision if any two indices
are not distinguishable if they are closer than $\epsilon_{2}$. This can
happen for example when indices must be communicated to other players in a
finite number of bits.

Thus, the cost $C$ is a function of $\epsilon_{1}$ and $\epsilon_{2}$, and can
be denoted as $C(\epsilon_{1},\epsilon_{2})$, with
$C(\epsilon_{1},\epsilon_{2})\rightarrow\infty$ as $\epsilon_{1}$ or
$\epsilon_{2}\rightarrow 0$. Since, $\epsilon_{1}$ and $\epsilon_{2}$ are the
parameters that are fixed a priori, we consider
$\epsilon=\min(\epsilon_{1},\epsilon_{2})$ to specify both precisions. We
denote the cost as $C(\epsilon)$.

We first show that if $\Delta_{min}$ is known, we can choose an
$\epsilon<\Delta_{min}/(M+1)$, so that ${\tt dUCB_{4}}$ algorithm will achieve
order log-squared regret growth with $T$. If $\Delta_{min}$ is not known, we
can pick a positive monotone sequence $\\{\epsilon_{t}\\}$ such that
$\epsilon_{t}\to 0$, as $t\to\infty$. In a decentralized bipartite matching
algorithm, the precision $\epsilon$ will depend on the amount of information
exchanged in the decision frames. It, thus, is some monotonically decreasing
function $\epsilon=f(L)$ of their length $L$ such that $\epsilon\to 0$ as
$L\to\infty$. Thus, we must pick a positive monotone sequence $\\{L_{t}\\}$
such that $L_{t}\to\infty$. Clearly, $C(f(L_{t}))\to\infty$ as $t\to\infty$.
This can happen arbitrarily slowly.

######  Theorem 6.

(i) Let $\epsilon>0$ be the precision of the bipartite matching algorithm and
the precision of the index representation. If $\Delta_{min}$ is known, choose
$\epsilon>0$ such that $\epsilon<\Delta_{min}/(M+1)$. Let $L$ be the length of
a frame. Then, the expected regret of the ${\tt dUCB_{4}}$ algorithm is

$\displaystyle\tilde{\mathcal{R}}_{\tt dUCB_{4}}(T)$ $\displaystyle\leq$
$\displaystyle(L\Delta_{max}+C(f(L))(1+\log
T))\cdot\left(\frac{4M^{3}(M+2)N\log
T}{(\Delta_{min}-((M+1)\epsilon)^{2}}+NM(2M+1)\right).$

Thus, $\tilde{\mathcal{R}}_{\tt dUCB_{4}}(T)=O(\log^{2}T).$
(ii) When $\Delta_{min}$ is unknown, denote
$\epsilon_{min}=\Delta_{min}/(2(M+1))$ and let $L_{t}\rightarrow\infty$ as
$t\rightarrow\infty$. Then, there exists a $t_{0}>0$ such that for all
$T>t_{0}$,

$\displaystyle\tilde{\mathcal{R}}_{\tt dUCB_{4}}(T)$
$\displaystyle\leq(L_{t_{0}}\Delta_{max}+C(f(L_{t_{0}}))t_{0}+(L_{T}\Delta_{max}+C(f(L_{T}))(1+\log
T))\cdot$ $\displaystyle\hskip 56.9055pt\left(\frac{4M^{3}(M+2)N\log
T}{(\Delta_{min}-\epsilon_{min})^{2}}+NM(2M+1)\right),$

where $t_{0}$ is the smallest $t$ such that $f(L_{t_{0}})<\epsilon_{min}$.
Thus by choosing an arbitrarily slowly increasing sequence $\\{L_{t}\\}$ we
can make the regret arbitrarily close to $\log^{2}T$.

###### Proof.

(i) First, we obtain a bound for $L=1$. Then, appeal to a result like Theorem
1 to obtain the result for general $L$. The implicit dependence between
$\epsilon$ and $L$ through the function $f(\cdot)$ does not affect this part
of the analysis. Details are omitted due to space limitations.

We first upper bound the number of sub-optimal plays. We define
$\tilde{n}_{i,j}(t),1\leq i\leq M,1\leq j\leq N$ as follows: Whenever the
${\tt dBM_{\epsilon}}(g(t))$ algorithm gives a non-optimal matching
$\mathbf{k}(t)$, $\tilde{n}_{i,j}(t)$ is increased by one for some
$(i,j)\in\arg\min_{1\leq i\leq M,1\leq j\leq N}n_{i,j}(t)$. Let $\tilde{n}(T)$
denote the total number of suboptimal plays. Then, clearly,
$\tilde{n}(T)=\sum_{i=1}^{M}\sum_{j=1}^{N}\tilde{n}_{i,j}(T)$. So, in order to
get a bound on $\tilde{n}(T)$ we first get a bound on $\tilde{n}_{i,j}(T)$.

Let $\tilde{I}_{i,j}(t)$ be the indicator function which is equal to $1$ if
$\tilde{n}_{i,j}(t)$ is incremented by one, at time $t$. When
$\tilde{I}_{i,j}(t)=1$, there will be a corresponding matching
$\mathbf{k}(t)\neq\mathbf{k}^{**}$ such that $k_{i}(t)=j$. In the following,
we denote it as $\mathbf{k}$, omitting the time index. A non-optimal matching
$\mathbf{k}$ is selected if the event
$\bigg{\\{}\sum_{i=1}^{M}g_{i,k^{**}_{i}}(m+2^{p}-1)\leq(M+1)\epsilon+\sum_{i=1}^{M}g_{i,k_{i}}(m+2^{p}-1)\bigg{\\}}$
happens. If each index has an error of at most $\epsilon$, the sum of $M$
terms may introduce an error of atmost $M\epsilon$. In addition, the
distributed bipartite matching algorithm ${\tt dBM_{\epsilon}}$ itself yields
only an $\epsilon$-optimal matching. This accounts for the term
$(M+1)\epsilon$ above. Since the initial steps are similar to that in Theorem
2, we skip those steps. Thus, similar to the equation (III-B), we get
$\tilde{n}_{i,j}(T)\leq$

$\displaystyle l$ $\displaystyle+$
$\displaystyle\sum_{m=1}^{T}\sum_{p=0}^{\infty}2^{p}I\bigg{\\{}\sum_{i=1}^{M}g_{i,k^{**}_{i}}(m+2^{p}-1)\leq(M+1)\epsilon+\sum_{i=1}^{M}g_{i,k_{i}}(m+2^{p}-1),\tilde{n}_{i,j}(m-1)\geq
l\bigg{\\}}$ $\displaystyle\leq$ $\displaystyle
l+\sum_{m=1}^{T}\sum_{p=0}^{\infty}2^{p}I\bigg{\\{}\sum_{i=1}^{M}\bigg{(}\overline{X}_{i,k^{**}_{i}}(m+2^{p}-1)+c_{m+2^{p}-1,n_{i,k^{**}_{i}}(m+2^{p}-1)}\bigg{)}$
$\displaystyle\hskip
56.9055pt\leq(M+1)\epsilon+\sum_{i=1}^{M}\overline{X}_{i,k_{i}}(m+2^{p}-1)+c_{m+2^{p}-1,n_{i,k_{i}}(m+2^{p}-1)},\tilde{n}_{i,j}(m-1)\geq
l\bigg{\\}}$ (29) $\displaystyle\leq$ $\displaystyle
l+\sum_{m=1}^{T}\sum_{p=0}^{\infty}2^{p}I\bigg{\\{}\min_{1\leq
s_{1,k^{**}_{1}},\ldots,s_{M,k^{**}_{M}}<m+2^{p}}\sum_{i=1}^{M}\left(\overline{X}_{i,k^{**}_{i}}(m+2^{p}-1)+c_{m+2^{p}-1,s_{i,k^{**}_{i}}}\right)$
$\displaystyle\hskip 56.9055pt\leq(M+1)\epsilon+\max_{l\leq
s_{1,k_{1}}^{{}^{\prime}},\ldots,s_{M,k_{M}}^{{}^{\prime}}<m+2^{p}}\sum_{i=1}^{M}\left(\overline{X}_{i,k_{i}}(m+2^{p}-1)+c_{m+2^{p}-1,s_{i,k_{i}}^{{}^{\prime}}}\right)\bigg{\\}}$
$\displaystyle\leq
l+\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}\sum_{s_{1,k^{**}_{1}}=1}^{m+2^{p}}\ldots\sum_{s_{M,k^{**}_{M}}=1}^{m+2^{p}}\sum_{s^{{}^{\prime}}_{1,k_{1}}=1}^{m+2^{p}}\ldots\sum_{s^{{}^{\prime}}_{M,k_{M}}=1}^{m+2^{p}}I\bigg{\\{}\sum_{i=1}^{M}\left(\overline{X}_{i,k^{**}_{i}}(m+2^{p})+c_{m+2^{p},s_{i,k^{**}_{i}}}\right)$
$\displaystyle\hskip
113.81102pt\leq(M+1)\epsilon+\sum_{i=1}^{M}\left(\overline{X}_{i,k_{i}}(m+2^{p})+c_{m+2^{p},s_{i,k_{i}}^{{}^{\prime}}}\right)\bigg{\\}}.$

Now, it is easy to observe that the event

$\displaystyle\bigg{\\{}\sum_{i=1}^{M}\left(\overline{X}_{i,k^{**}_{i}}(m+2^{p})+c_{m+2^{p},s_{i,k^{**}_{i}}}\right)\leq(M+1)\epsilon+\sum_{i=1}^{M}\left(\overline{X}_{i,k_{i}}(m+2^{p})+c_{m+2^{p},s_{i,k_{i}}^{{}^{\prime}}}\right)\bigg{\\}}$

implies at least one of the following events:

$\displaystyle A_{i}$ $\displaystyle:=$
$\displaystyle\bigg{\\{}\overline{X}_{i,k^{**}_{i}}(m+2^{p})\leq\mu_{i,k^{**}_{i}}-c_{m+2^{p},s_{i,k^{**}_{i}}}\bigg{\\}},$
$\displaystyle B_{i}$ $\displaystyle:=$
$\displaystyle\bigg{\\{}\overline{X}_{i,k_{i}}(m+2^{p})\geq\mu_{i,k_{i}}+c_{m+2^{p},s_{i,k_{i}}^{{}^{\prime}}}\bigg{\\}},1\leq
i\leq M,$ $\displaystyle C$ $\displaystyle:=$
$\displaystyle\bigg{\\{}\sum_{i=1}^{M}\mu_{i,k^{**}_{i}}<(M+1)\epsilon+\sum_{i=1}^{M}\mu_{i,k_{i}}+2\sum_{i=1}^{M}c_{m+2^{p},s_{i,k_{i}}^{{}^{\prime}}}\bigg{\\}}$
(30) $\displaystyle D$ $\displaystyle:=$
$\displaystyle\bigg{\\{}(M+1)\epsilon>\sum_{i=1}^{M}\mu_{i,k^{**}_{i}}-\sum_{i=1}^{M}\mu_{i,k_{i}}\bigg{\\}}.$

Using the Chernoff-Hoeffding inequality, we get
$\mathbb{P}(A_{i})\leq(m+2^{p})^{-2(M+2)},~{}~{}\mathbb{P}(B_{i})\leq(m+2^{p})^{-2(M+2)},~{}1\leq
i\leq M.$ For $l\geq\left\lceil\frac{4M^{2}(M+2)\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}\right\rceil$, we get
$\sum_{i=1}^{M}\mu_{i,k^{**}_{i}}-\sum_{i=1}^{M}\mu_{i,k_{i}}-(M+1)\epsilon-2\sum_{i=1}^{M}c_{m+2^{p},s_{i,k_{i}}^{{}^{\prime}}}$

$\displaystyle\geq$
$\displaystyle\sum_{i=1}^{M}\mu_{i,k^{**}_{i}}-\sum_{i=1}^{M}\mu_{i,k_{i}}-(M+1)\epsilon-2M\sqrt{\frac{(M+2)\log(m+2^{p})}{l}}$
(31) $\displaystyle\geq$
$\displaystyle\sum_{i=1}^{M}\mu_{i,k^{**}_{i}}-\sum_{i=1}^{M}\mu_{i,k_{i}}-(M+1)\epsilon-(\Delta_{min}-(M+1)\epsilon)\geq
0$

The event $D$ is false by assumption. So, we get,
$\mathbb{E}[\tilde{n}_{i,j}(T)]$

$\displaystyle\leq\left\lceil\frac{4M^{2}(M+2)\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}\right\rceil+\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}\sum_{s_{1,k^{**}_{1}}=1}^{m+2^{p}}\ldots\sum_{s_{M,k^{**}_{M}}=1}^{m+2^{p}}\sum_{s^{{}^{\prime}}_{1,k_{1}}=1}^{m+2^{p}}\ldots\sum_{s^{{}^{\prime}}_{M,k_{M}}=1}^{m+2^{p}}2M(m+2^{p})^{-2(M+2)}$
$\displaystyle\leq\left\lceil\frac{4M^{2}(M+2)\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}\right\rceil+2M\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}(m+2^{p})^{-4}$
$\displaystyle\leq\frac{4M^{2}(M+2)\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}+(2M+1).$ (32)

Now, putting it all together, we get

$\displaystyle\mathbb{E}[\tilde{n}(T)]$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{M}\sum_{j=1}^{N}\mathbb{E}[\tilde{n}_{i,j}(T)]\leq\frac{4M^{3}(M+2)N\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}+(2M+1)MN.$

Now, by the proof of Theorem 2 (c.f. equation(15),
$\mathbb{E}[m(T)]\leq\mathbb{E}[\tilde{n}(T)](1+\log T).$ We can now bound the
regret, $\tilde{\mathcal{R}}_{\tt dUCB_{4}}(T)=\sum_{k\in\mathcal{P}(N),k\neq
k^{**}}\Delta_{k}\sum_{i=1}^{M}\mathbb{E}[\tilde{n}_{i,k_{i}}(T)]+C\mathbb{E}[m(T)]$

$\displaystyle\leq$ $\displaystyle\Delta_{max}\sum_{k\in\mathcal{P}(N),k\neq
k^{**}}\sum_{i=1}^{M}\mathbb{E}[\tilde{n}_{i,k_{i}}(T)]+C\mathbb{E}[m(T)]$
$\displaystyle=$
$\displaystyle\Delta_{max}\mathbb{E}[\tilde{n}(T)]+C\mathbb{E}[m(t)].$

For a general $L$, by Theorem 1 we get

$\displaystyle\tilde{\mathcal{R}}_{\tt dUCB_{4}}(T)\leq
L\Delta_{max}\mathbb{E}[\tilde{n}(T)]+C(f(L))\mathbb{E}[m(T)]\leq(L\Delta_{max}+C(f(L))(1+\log
T))\mathbb{E}[\tilde{n}(T)].$

Now, using the bound (V), we get the desired upper bound on the expected
regret.
(ii) Since $\epsilon_{t}=f(L_{t})$ is a monotonically decreasing function of
$L_{t}$ such that $\epsilon_{t}\to 0$ as $L_{t}\to\infty$, there exists a
$t_{0}$ such that for $t>t_{0}$, $\epsilon_{t}<\epsilon_{min}$. We may get a
linear regret upto time $t_{0}$ but after that by the analysis of Theorem 2,
regret grows only sub-linearly. Since $C(\cdot)$ is monotonically increasing,
$C(f(L_{T}))\geq C(f(L_{t})),\forall t\leq T$, we get the desired result. The
last part is illustrative and can be trivially established using the obtained
bound on the regret in (ii). ∎

Remarks. 1\. We note that in the initial steps, our proof followed the proof
of the main result in [12].
2\. The ${\tt UCB_{2}}$ algorithm described in [4] performs computations only
at exponentially spaced time epochs. So, it is natural to imagine that a
decentralized algorithm based on it could be developed, and get a better
regret bound. Unfortunately, the single player ${\tt UCB_{2}}$ algorithm has
an obvious weakness: regret is linear in the number of arms. Thus, the
decentralized/combinatorial extension of ${\tt UCB_{2}}$ would yield regret
growing exponentially in the number of players and arms. We use a similar
index but a different scheme, allowing us to achieve poly-log regret growth
and a linear memory requirement for each player.

##  VI The Decentralized MAB problem with Markovian rewards

Now, we consider the decentralized MAB problem with $M$ players and $N$ arms
where the rewards obtained each time when an arm is pulled are not i.i.d. but
come from a Markov chain. The reward that player $i$ gets from arm $j$ (when
there is no collision) $X_{ij}$, is modelled as an irreducible, aperiodic,
reversible Markov chain on a finite state space $\mathcal{X}^{i,j}$ and
represented by a transition probability matrix
$P^{i,j}:=\left(p^{i,j}_{x,x^{{}^{\prime}}}:x,x^{{}^{\prime}}\in\mathcal{X}^{i,j}\right)$.
Assume that $\mathcal{X}^{i,j}\in(0,1]$. Let $X_{i,j}(1),X_{i,j}(2),\ldots$
denote the successive rewards from arm $j$ for player $i$. All arms are
mutually independent for all players. Let
$\mathbf{\pi}^{i,j}:=\left(\pi^{i,j}_{x},x\in\mathcal{X}^{i,j}\right)$ be the
stationary distribution of the Markov chain $P^{i,j}$. The mean reward from
arm $j$ for player $i$ is defined as
$\mu_{i,j}:=\sum_{x\in\mathcal{X}^{i,j}}x\pi^{i,j}_{x}$. Note that the Markov
chain represented by $P^{i,j}$ makes a state transition only when player $i$
plays arm $j$. Otherwise, it remains _rested_. As described in the previous
section, $n_{i}(t)$ is the number of successful plays (without collisions) of
player $i$ by frame $t$, $n_{i,j}(t)$ is the number of times player $i$ picks
arm $j$ successfully by frame $t$ and $\overline{X}_{i,j}(t)$ is the sample
mean of rewards from arm $j$ for player $i$ from $n_{i,j}(t)$ samples. Denote
$\Delta_{min}:=\min_{\mathbf{k}\in\mathcal{P}(N),\mathbf{k}\neq\mathbf{k}^{**}}\Delta_{\mathbf{k}}$
and $\Delta_{max}:=\max_{\mathbf{k}\in\mathcal{P}(N)}\Delta_{\mathbf{k}}$.
Denote $\pi_{min}:=\min_{1\leq i\leq M,1\leq j\leq
N,x\in\mathcal{X}^{i,j}}\pi^{i,j}_{x}$, $x_{max}:=\max_{1\leq i\leq M,1\leq
j\leq N,x\in\mathcal{X}^{i,j}}x$ and $x_{min}:=\min_{1\leq i\leq M,1\leq j\leq
N,x\in\mathcal{X}^{i,j}}x$. Let
${\hat{\pi}^{i,j}}_{x}:=\max\\{\pi^{i,j}_{x},1-\pi^{i,j}_{x}\\}$ and
$\hat{\pi}_{max}:=\max_{1\leq i\leq M,1\leq j\leq
N,x\in\mathcal{X}^{i,j}}{\hat{\pi}^{i,j}}_{x}$. Let $|\mathcal{X}^{i,j}|$
denote the cardinality of the state space $\mathcal{X}^{i,j}$,
$|\mathcal{X}|_{max}:=\max_{1\leq i\leq M,1\leq j\leq N}|\mathcal{X}^{i,j}|$.
Let $\rho^{i,j}$ be the eigenvalue gap, $1-\lambda_{2}$, where $\lambda_{2}$
is the second largest eigenvalue of the matrix ${P^{i,j}}^{2}$. Denote
$\rho_{max}:=\max_{1\leq i\leq M,1\leq j\leq N}\rho^{i,j}$ and
$\rho_{min}:=\min_{1\leq i\leq M,1\leq j\leq N}\rho^{i,j}$.

The total reward obtained by time $T$ is
$S_{T}=\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{s=1}^{n_{i,j}(T)}X_{i,j}(s)$ and the
regret is

$\tilde{\mathcal{R}}_{M,\alpha}(T):=T\sum_{i=1}^{M}\mu_{i,k_{i}^{**}}-\mathbb{E}_{\alpha}\left[\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{s=1}^{n_{i,j}(T)}X_{i,j}(s)\right]+C\mathbb{E}[m(T)].$
(33)

Define the index

$g_{i,j}(t):=\overline{X}_{i,j}(t)+\sqrt{\frac{\kappa\log
n_{i}(t)}{n_{i,j}(t)}}$ (34)

where $\kappa$ be any constant such that
$\kappa>(112+56M)|\mathcal{X}|_{max}^{2}/\rho_{min}$.

We need the following lemma to prove the regret bound.

######  Lemma 2.

If the reward of each player-arm pair $(i,j)$ is given by a Markov chain,
satisfying the properties of Lemma 4, then under any policy $\alpha$

$\tilde{\mathcal{R}}_{M,\tt\alpha}(T)\leq\sum_{k\in\mathcal{P}(N),k\neq
k^{**}}\Delta_{k}\mathbb{E}[n^{k}(T)]+C\mathbb{E}[m(T)]+\tilde{K}_{\mathcal{X},P}$
(35)

where $n^{k}(T)$ is the number of times that the matching $k$ occurred by the
time $T$ and $\tilde{K}_{\mathcal{X},P}$ is defined as
$\tilde{K}_{\mathcal{X},P}=\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{x\in\mathcal{X}^{i,j}}x/\pi^{j}_{min}$

###### Proof.

Let $(X_{i,j}(1),X_{i,j}(2),\ldots)$ denote the successive rewards for player
$i$ from arm $j$. Let $\mathcal{F}^{i,j}_{t}$ denote the $\sigma$-algebra
generated by $(X_{i,j}(1),\ldots,X_{i,j}(t))$, $\mathcal{F}^{i,j}=\vee_{t\geq
1}\mathcal{F}^{i,j}_{t}$ and $\mathcal{G}^{i,j}=\vee_{(k,l)\neq(i,j)}F^{k,l}$.
Since arms are independent, $\mathcal{G}^{i,j}$ is independent of
$\mathcal{F}^{i,j}$. Clearly, $n_{i,j}(T)$ is a stopping time with respect to
$\mathcal{F}^{i,j}\vee\mathcal{G}^{i,j}_{T}$. The total reward is

$S_{T}=\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{t=1}^{n_{i,j}(T)}X_{i,j}(t)=\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{x\in\mathcal{X}^{i,j}}xN(x,n_{i,j}(T))$

where $N(x,n_{i,j}(T)):=\sum_{t=1}^{n_{i,j}(T)}I\\{X_{i,j}(t)=x\\}$. Taking
expectations and using the Lemma 4,

$\left\lvert\mathbb{E}[S_{T}]-\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{x\in\mathcal{X}^{i,j}}x\pi^{i,j}_{x}\mathbb{E}[n_{i,j}(T)]\right\rvert\leq\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{x\in\mathcal{X}^{i,j}}x/\pi^{i,j}_{min}$

which implies,

$\left\lvert\mathbb{E}[S_{T}]-\sum_{j=1}^{N}\sum_{i=1}^{M}\mu_{i,j}\mathbb{E}[n_{i,j}(T)]\right\rvert\leq\tilde{K}_{\mathcal{X},P}$

where
$\tilde{K}_{\mathcal{X},P}=\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{x\in\mathcal{X}^{i,j}}x/\pi^{i,j}_{min}$.
Now,

$\displaystyle\sum_{j=1}^{N}\sum_{i=1}^{M}\mu_{i,j}\mathbb{E}[n_{i,j}(T)]$
$\displaystyle=\sum_{j=1}^{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{P}(N),(i,j)\in
k}\mu_{i,k_{i}}\mathbb{E}[n_{i,k_{i}}(T)]=\sum_{k\in\mathcal{P}(N)}\sum_{i=1}^{M}\mu_{i,k_{i}}\mathbb{E}[n_{i,k_{i}}(T)]$
$\displaystyle=\sum_{k\in\mathcal{P}(N)}\mu^{k}\mathbb{E}[n^{k}(T)]$

where $\mu^{k}=\sum_{i=1}^{M}\mu_{i,k_{i}}$. Since regret is defined as in the
equation (33),

$\left\lvert\tilde{\mathcal{R}}_{M,\alpha}(T)-\left(T\mu^{**}-\sum_{k\in\mathcal{P}(N),(i,j)\in
k}\mu_{i,k_{i}}\mathbb{E}[n_{i,k_{i}}(T)]+C\mathbb{E}_{\alpha}[m(T)]\right)\right\rvert\leq\tilde{K}_{\mathcal{X},P}.$
(36)

∎

The main result of this section is the following.

######  Theorem 7.

(i) Let $\epsilon>0$ be the precision of the bipartite matching algorithm and
the precision of the index representation. If $\Delta_{min}$,
$|\mathcal{X}|_{max}$ and $\rho_{min}$ are known, choose $\epsilon>0$ such
that $\epsilon<\Delta_{min}/(M+1)$ and
$\kappa>(112+56M)|\mathcal{X}|_{max}^{2}/\rho_{min}$. Let $L$ be the length of
a frame. Then, the expected regret of the ${\tt dUCB_{4}}$ algorithm with
index (34) for the decentralized MAB problem with Markovian rewards and per
computation cost $C$ is given by
$\tilde{\mathcal{R}}_{M,\tt dUCB_{4}}(T)$

$\displaystyle\leq$ $\displaystyle(L\Delta_{max}+C(f(L))(1+\log
T))\cdot\left(\frac{4M^{3}\kappa N\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}+(2MD+1)MN\right)+\tilde{K}_{\mathcal{X},P}.$

Thus, $\tilde{\mathcal{R}}_{M,\tt dUCB_{4}}(T)=O(\log^{2}T).$
(ii) If $\Delta_{min}$, $|\mathcal{X}|_{max}$ and $\rho_{min}$ are unknown,
denote $\epsilon_{min}=\Delta_{min}/(2(M+1))$ and let $L_{t}\rightarrow\infty$
as $t\rightarrow\infty$. Also, choose a positive monotone sequence
$\\{\kappa_{t}\\}$ such that $\kappa_{t}\rightarrow\infty$ as
$t\rightarrow\infty$ and $\kappa_{t}\leq t$. Then, $\tilde{\mathcal{R}}_{M,\tt
dUCB_{4}}(T)=O(C(f(L_{T}))\kappa_{T}\log^{2}T)$. Thus by choosing an
arbitrarily-slowly increasing sequences, we can make the regret arbitrarily
close to $\log^{2}T$.

###### Proof.

(i) We skip the initial steps as they are same as in the proof of Theorem 6.
We start by bounding $\tilde{n}_{i,j}(T)$ as defined in the proof of Theorem
6. Then, from equation (V), we get $\tilde{n}_{i,j}(T)$

$\displaystyle\leq
l+\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}\sum_{s_{1,k^{**}_{1}}=1}^{m+2^{p}}\ldots\sum_{s_{M,k^{**}_{M}}=1}^{m+2^{p}}\sum_{s^{{}^{\prime}}_{1,k_{1}}=1}^{m+2^{p}}\ldots\sum_{s^{{}^{\prime}}_{M,k_{M}}=1}^{m+2^{p}}I\\{\sum_{i=1}^{M}\left(\overline{X}_{i,k^{**}_{i}}(m+2^{p})+c_{m+2^{p},s_{i,k^{**}_{i}}}\right)$
$\displaystyle\hskip
113.81102pt\leq(M+1)\epsilon+\sum_{i=1}^{M}\left(\overline{X}_{i,k_{i}}(m+2^{p})+c_{m+2^{p},s_{i,k_{i}}^{{}^{\prime}}}\right)\\}$
(37)

Now, the event in the parenthesis $\\{\cdot\\}$ above implies at least one of
the events ($A_{i},B_{i},C,D$) given in the display (V). From the proof of
Theorem 4 (equations (22, 23), $\mathbb{P}(A_{i})\leq
D(m+2^{p})^{-\frac{\kappa\rho_{min}}{28|\mathcal{X}|_{max}|^{2}}},\hskip
28.45274pt\mathbb{P}(B_{i})\leq
D(m+2^{p})^{-\frac{\kappa\rho_{min}}{28|\mathcal{X}|_{max}|^{2}}},1\leq i\leq
M.$ Similar to the steps in display (31), we can show that the event $C$ is
false. Also, the event $D$ is false by assumption. So, similar to the proof of
the Theorem 6 (c.f. display (V) we get,

$\displaystyle\mathbb{E}[\tilde{n}_{i,j}(T)]$ $\displaystyle\leq$
$\displaystyle\left\lceil\frac{4M^{2}\kappa\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}\right\rceil+\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}\sum_{s_{1,k^{**}_{1}}=1}^{m+2^{p}}\ldots\sum_{s_{M,k^{**}_{M}}=1}^{m+2^{p}}$
$\displaystyle\hskip
85.35826pt\sum_{s^{{}^{\prime}}_{1,k_{1}}=1}^{m+2^{p}}\ldots\sum_{s^{{}^{\prime}}_{M,k_{M}}=1}^{m+2^{p}}2MD(m+2^{p})^{-\frac{\kappa\rho_{min}}{28|\mathcal{X}|_{max}|^{2}}}$
$\displaystyle\leq$ $\displaystyle\left\lceil\frac{4M^{2}\kappa\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}\right\rceil+2MD\sum_{m=1}^{\infty}\sum_{p=0}^{\infty}2^{p}(m+2^{p})^{-\frac{\kappa\rho_{min}-56M|\mathcal{X}|_{max}^{2}}{28|\mathcal{X}|_{max}^{2}}}$
$\displaystyle\leq$ $\displaystyle\frac{4M^{2}\kappa\log
T}{(\Delta_{min}-(M+1)\epsilon)^{2}}+(2MD+1).$

when $\kappa>(112+56M)|\mathcal{X}|_{max}^{2}/\rho_{min}$. Now, putting it all
together, we get

$\displaystyle\mathbb{E}[\tilde{n}(T)]$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{M}\sum_{j=1}^{N}\mathbb{E}[\tilde{n}_{i,j}(T)]\leq\frac{4M^{3}\kappa
N\log T}{(\Delta_{min}-(M+1)\epsilon)^{2}}+(2MD+1)MN.$

Now, by proof of the Theorem 2 (equation (15)),
$\mathbb{E}[m(T)]\leq\mathbb{E}[\tilde{n}(T)](1+\log T).$ We can now bound the
regret,

$\displaystyle\tilde{\mathcal{R}}_{M,\tt dUCB_{4}}(T)$ $\displaystyle=$
$\displaystyle\sum_{k\in\mathcal{P}(N),k\neq
k^{**}}\Delta_{k}\sum_{i=1}^{M}\mathbb{E}[\tilde{n}_{i,k_{i}}(T)]+C\mathbb{E}[m(T)]+\tilde{K}_{\mathcal{X},P}$
$\displaystyle\leq$ $\displaystyle\Delta_{max}\sum_{k\in\mathcal{P}(N),k\neq
k^{**}}\sum_{i=1}^{M}\mathbb{E}[\tilde{n}_{i,k_{i}}(T)]+C\mathbb{E}[m(T)]+\tilde{K}_{\mathcal{X},P}$
$\displaystyle=$
$\displaystyle\Delta_{max}\mathbb{E}[\tilde{n}(T)]+C\mathbb{E}[m(T)]+\tilde{K}_{\mathcal{X},P}.$

For a general $L$, by Theorem 1

$\displaystyle\tilde{\mathcal{R}}_{M,\tt dUCB_{4}}(T)$ $\displaystyle\leq$
$\displaystyle
L\Delta_{max}\mathbb{E}[\tilde{n}(T)]+C(f(L))\mathbb{E}[m(T)]+\tilde{K}_{\mathcal{X},P}.$
$\displaystyle\leq$ $\displaystyle(L\Delta_{max}+C(f(L))(1+\log
T))\mathbb{E}[\tilde{n}(T)]+\tilde{K}_{\mathcal{X},P}.$

Now, using the bound (VI), we get the desired upper bound on the expected
regret.
(ii) This can now easily be obtained using the above and following Theorem 6.
∎

##  VII Distributed Bipartite Matching: Algorithm and Implementation

In the previous section, we referred to an unspecified distributed algorithm
for bipartite matching ${\tt dBM}$, that is used by the ${\tt dUCB_{4}}$
algorithm. We now present one such algorithm, namely, Bertsekas’ auction
algorithm [17], and its distributed implementation. We note that the presented
algorithm is not the only one that can be used. The ${\tt dUCB_{4}}$ algorithm
will work with a distributed implementation of any bipartite matching
algorithm, e.g. algorithms given in [24].

Consider a bipartite graph with $M$ players on one side, and $N$ arms on the
other, and $M\leq N$. Each player $i$ has a value $\mu_{i,j}$ for each arm
$j$. Each player knows only his own values. Let us denote by $k^{**}$, a
matching that maximizes the matching surplus $\sum_{i,j}\mu_{i,j}x_{i,j}$,
where the variable $x_{i,j}$ is 1 if $i$ is matched with $j$, and 0 otherwise.
Note that $\sum_{i}x_{i,j}\leq 1,\forall j$, and $\sum_{j}x_{i,j}\leq
1,\forall i$. Our goal is to find an $\epsilon$-optimal matching. We call any
matching $k^{*}$ to be $\epsilon$-optimal if
$\sum_{i}\mu_{i,k^{**}(i)}-\sum_{i}\mu_{i,k^{*}(i)}\leq\epsilon$.

Algorithm 3 : ${\tt dBM_{\epsilon}}$ ( Bertsekas Auction Algorithm)

1: All players $i$ initialize prices $p_{j}=0,\forall~{}\text{channels}~{}j$;

2: while (prices change) do

3: Player $i$ communicates his preferred arm $j_{i}^{*}$ and bid
$b_{i}=\max_{j}(\mu_{ij}-p_{j})-\text{2max}_{j}(\mu_{ij}-p_{j})+\frac{\epsilon}{M}$
to all other players.

4: Each player determines on his own if he is the winner $i_{j}^{*}$ on arm
$j$;

5: All players set prices $p_{j}=\mu_{i_{j}^{*},j}$;

6: end while

Here, $\text{2max}_{j}$ is the second highest maximum over all $j$. The best
arm for a player $i$ is arm $j_{i}^{*}=\arg\max_{j}(\mu_{i,j}-p_{j})$. The
winner $i_{j}^{*}$ on an arm $j$ is the one with the highest bid.

The following lemma in [17] establishes that Bertsekas’ auction algorithm will
find the $\epsilon$-optimal matching in a finite number of steps.

######  Lemma 3.

[17] Given $\epsilon>0$, Algorithm 3 with rewards $\mu_{i,j}$, for player $i$
playing the $j$th arm, converges to a matching $k^{*}$ such that
$\sum_{i}\mu_{i,k^{**}(i)}-\sum_{i}\mu_{i,k^{*}(i)}\leq\epsilon$ where
$k^{**}$ is an optimal matching. Furthermore, this convergence occurs in less
than $(M^{2}\max_{i,j}\\{\mu_{i,j}\\})/\epsilon$ iterations.

The temporal structure of the ${\tt dUCB_{4}}$ algorithm is such that time is
divided into frames of length $L$. Each frame is either a decision frame, or
an exploitation frame. In the exploitation frame, each player plays the arm it
was allocated in the last decision frame. The distributed bipartite matching
algorithm (e.g. based on Algorithm 3), is run in the decision frame. The
decision frame has an interrupt phase of length $M$ and negotiation phase of
length $L-M$. We now describe an implementation structure for these phases in
the decision frame.

Figure 1: Structure of the decision frame

Interrupt Phase: The interrupt phase can be implemented very easily. It has
length $M$ time slots. On a pre-determined channel, each player by turn
transmits a ‘1’ if the arm with which it is now matched has changed, ‘0’
otherwise. If any user transmits a ‘1’, everyone knows that the matching has
changed, and they reset their counter $\eta=1$.

Negotiation Phase: The information needed to be exchanged to compute an
$\epsilon$-optimal matching is done in the negotiation phase. We first provide
a packetized implementation of the negotiation phase. The negotiation phase
consists of $J$ subframes of length $M$ each (See figure 1). In each subframe,
the users transmit a packet by turn. The packet contains bid information:
(channel number, bid value). Since all users transmit by turn, all the users
know the bid values by the end of the subframe, and can compute the new
allocation, and the prices independently. The length of the subframe $J$
determines the precision $\epsilon$ of the distributed bipartite matching
algorithm. Note that in the packetized implementation, $\epsilon_{1}=0$, i.e.,
bid values can be computed exactly, and for a given $\epsilon_{2}$, we can
determine $J$, the number of rounds the ${\tt dBM}$ algorithm 3 runs for, and
returns an $\epsilon_{2}$-optimal matching.

If a packetized implementation is not possible, we can give a physical
implementation. Our only assumption here is going to be that each user can
observe a channel, and determine if there was a successful transmission on it,
a collision, or no transmission, in a given time slot. The whole negotiation
phase is again divided into $J$ sub-frames. In each sub-frame, each user
transmits by turn. It simply transmits $\lceil{\log M}\rceil$ bits to indicate
a channel number, and then $\lceil{\log 1/\epsilon_{1}}\rceil$ bits to
indicate its bid value to precision $\epsilon_{1}$. The number of such sub-
frames $J$ is again chosen so that the ${\tt dBM}$ algorithm (based on
Algorithm 3) returns an $\epsilon_{2}$-optimal matching.

##  VIII Simulations

Figure 2: (i) Cumulative regret : $2$ users, $2$ channels; i.i.d. channels;
Mean reward matrix = $[0.8,0.6;0.6,0.35]$. (ii) Cumulative regret : $2$ users,
$2$ channels; Markovian channels.

We illustrate the empirical performance of the ${\tt dUCB_{4}}$ algorithm when
the successive rewards from a channel are i.i.d. and when they are Markovian.
Consider two users and two channels. In the i.i.d. case, each channel has
rewards that are generated by a Bernoulli distribution taking values $0$ and
$1$. The first user has mean rewards of $0.8$ and $0.6$ for channels $1$ and
$2$ respectively. The second user has mean rewards of $0.6$ and $0.35$. The
algorithm’s performance, averaged over 50 runs, is shown in Figure 2 (i). It
shows cumulative regret with time. The red bold curve is the theoretical upper
bound we derived, while the blue curve is the observed regret. The algorithm
seems to perform much better than even the poly-log regret upper bound we
derived.

In the Markovian case, rewards are generated by a Markov chain having states
$0$ and $1$. The mean reward on a channel is given by its stationary
distribution, i.e., the probability the Markov chain is in state $1$,
$\pi_{1}$. The properties of the Markov chains are given in Table I. The
performance of the ${\tt dUCB_{4}}$ algorithm on this model, averaged over 50
runs, is shown in Figure 2 (ii). Once again, the algorithm seems to perform
much better than even the poly-log regret upper bound we derived.

TABLE I: Markov Chain Parameters : Transition probability and Stationary distribution User | Channel |  $p_{01}$,$p_{10}$ | $\pi$
---|---|---|---
1 | 1 |  $0.3$,$0.5$ | $0.3/0.8$
1 | 2 |  $0.2$,$0.6$ | $0.2/0.8$
2 | 1 |  $0.6$,$0.3$ | $0.6/0.9$
2 | 2 |  $0.7$,$0.2$ | $0.7/0.9$

##  IX Conclusions

We have proposed a ${\tt dUCB_{4}}$ algorithm for decentralized learning in
multi-armed bandit problems that achieves a regret of near-$O(\log^{2}(T))$.
Finding a lower bound is usually quite difficult, and currently a work in
progress.

## References

  * [1] T. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” _Advances in Applied Mathematics_ , vol. 6, no. 1, pp. 4-22, 1985.
  * [2] V. Anantharam, P. Varaiya, and J. Walrand, “Asymptotically efficient allocation rules for the multi-armed bandit problem with multiple plays - part i: i.i.d. rewards,” _IEEE Transactions on Automatic Control_ , vol. 32, no. 11, pp. 968-975, November, 1987.
  * [3] R. Agrawal, “Sample mean based index policies with (${O}(\log n)$) regret for the multi-armed bandit problem,” _Advances in Applied Probability_ , Vol. 27, No. 4, pp. 1054-1078, 1995.
  * [4] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” _Machine Learning_ , vol. 47, no. 2, pp. 235-256, 2002.
  * [5] V. Anantharam, P. Varaiya, and J. Walrand, “Asymptotically efficient allocation rules for the multi-armed bandit problem with multiple plays - part ii: Markovian rewards,” _IEEE Transactions on Automatic Control_ , vol. 32, no. 11, pp. 977-982, November 1987.
  * [6] C. Tekin and M. Liu, “Online algorithms for the multi-armed bandit problem with markovian rewards,” _Allerton Conference on Communication, Control, and Computing_ , October, 2010.
  * [7] C. Papadimitriou and J. Tsitsiklis, “The complexity of optimal queuing network control,” _Mathematics of Operations Research_ , vol. 24, no. 2, pp. 293-305, May, 1999.
  * [8] C. Tekin and M. Liu, “Online learning in opportunistic spectrum access: A restless bandit approach,” _International Conference on Computer Communications (INFOCOM), Shanghai, China._ , April 2011.
  * [9] W. Dai, Y. Gai, and B. Krishnamachari, “Efficient online learning for opportunistic spectrum access,” _International Conference on Computer Communications (INFOCOM), Mini Conference, Orlando, USA_ , March, 2012.
  * [10] H. Liu, K. Liu, and Q. Zhao, “Learning in a changing world: Restless multi-armed bandit with unknown dynamics,” _IEEE Transactions on Information Theory_ , Submitted, November, 2011.
  * [11] W. Dai, Y. Gai, B. Krishnamachari, and Q. Zhao, “The non-bayesian restless multi-armed bandit: A case of near-logarithmic regret,” _International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , May, 2011.
  * [12] Y. Gai, B. Krishnamachari, and R. Jain, “Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations,” _IEEE/ACM Trans. on Networking_ , to appear, 2012\.
  * [13] Y. Gai, B. Krishnamachari, and M. Liu, “On the combinatorial multi-armed bandit problem with markovian rewards,” _IEEE Global Communications Conference (GLOBECOM)_ , December, 2011.
  * [14] K. Liu and Q. Zhao, “Distributed learning in multi-armed bandit with multiple players,” _IEEE Transactions on Signal Processing_ , vol. 58, pp. 5667-5681, November, 2010.
  * [15] A. Anandkumar, N. Michael, A. Tang, and A. Swami, “Distributed algorithms for learning and cognitive medium access with logarithmic regret,” _IEEE JSAC on Advances in Cognitive Radio Networking and Communications_ , April, 2011\.
  * [16] Y. Gai and B. Krishnamachari, “Decentralized online learning algorithms for opportunistic spectrum access,” _IEEE Global Communications Conference (GLOBECOM 2011)_ , December, 2011.
  * [17] D. P. Bertsekas, “Auction algorithms for network flow problems: A tutorial introduction,” _Computational Optimization and Applications_ , vol. 1, pp. 7-66, 1992.
  * [18] E. Hossain and V. K. Bhargava, “Cognitive wireless communication networks,” _Springer_ , 2007.
  * [19] D. Pollard, “Convergence of stochastic processes,” _Springer_ , 1984.
  * [20] K. Liu and Q. Zhao, “Multi-armed bandit problems with heavy tail reward distributions,” _Allerton Conference on Communication, Control, and Computing_ , September, 2011.
  * [21] P. Lezaud, “Chernoff-type bound for finite markov chains,” _Ann. Appl. Prob._ , vol. 8, pp. 849-867, 1998.
  * [22] C. Tekin and M. Liu, “Online learning of rested and restless bandits,,” _IEEE Trans. on Information Theory_ , Submitted, 2012.
  * [23] D. P. Bertsekas, “The auction algorithm: A distributed relaxation method for the assignment problem,” _Annals of Operations Research_ , vol. 14, 1988\.
  * [24] M. Zavlanos, L. Spesivtsev, and G. J. Pappas, “A distributed auction algorithm for the assignment problem,” _Proceedings of the IEEE Conference on Decision and Control_ , December, 2008.

Let $\left(X_{t},t=1,2,\ldots\right)$ be an irreducible, aperiodic and
reversible Markov chain on a finite state space $\mathcal{X}$ with transition
probability matrix $P$, a stationary distribution $\pi$ and an initial
distribution $\lambda$. Let $\mathcal{F}_{t}$ be the $\sigma$-algebra
generated by $\left(X_{1},X_{2},\ldots,X_{t}\right)$. Denote
$N_{\lambda}=\left\lVert\left(\frac{\lambda_{x}}{\pi_{x}},x\in\mathcal{X}\right)\right\rVert_{2}$.

######  Lemma 4.

[5] Let $\mathcal{G}$ be a $\sigma$-algebra independent of
$\mathcal{F}=\vee_{t\geq 1}F_{t}$. Let $\tau$ be a stopping time of
$\mathcal{F}_{t}\vee\mathcal{G}$. Let
$N(x,\tau):=\sum_{t=1}^{\tau}I\\{X_{t}=x\\}$. Then,
$|\mathbb{E}[N(x,\tau)]-\pi_{x}\mathbb{E}[\tau]|\leq K,$ where $K\leq
1/\pi_{min}$ and $\pi_{min}=\min_{x\in\mathcal{X}}\pi_{x}$. $K$ depends on
$P$.

######  Lemma 5.

[21] Denote
$N_{\lambda}=\left\lVert\left(\frac{\lambda_{x}}{\pi_{x}},x\in\mathcal{X}\right)\right\rVert_{2}$.
Let $\rho$ be the eigenvalue gap, $1-\lambda_{2}$, where $\lambda_{2}$ is the
second largest eigenvalue of the matrix $P^{2}$. Let
$f:\mathcal{X}\rightarrow\mathbf{R}$ be such that
$\sum_{x\in\mathcal{X}}\pi_{x}f(x)=0$, $\left\lVert f\right\rVert_{\infty}\leq
1,{\left\lVert f\right\rVert}^{2}_{2}\leq 1$. Then, for any $\gamma>0$,
$\mathbb{P}\left(\sum_{a=1}^{t}f(X_{a})/t\geq\gamma\right)\leq
N_{\lambda}e^{-t\rho\gamma^{2}/28}.$