010007 2009 A. C. Martí 010007

When two immiscible liquids that coexist inside a porous medium are drained
through an opening, a complex flow takes place in which the interface between
the liquids moves, tilts and bends. The interface profiles depend on the
physical properties of the liquids and on the velocity at which they are
extracted. If the drainage flow rate, the liquids volume fraction in the
drainage flow and the physical properties of the liquids are known, the
interface angle in the immediate vicinity of the outlet ($\theta$) can be
determined. In this work, we define four nondimensional parameters that rule
the fluid dynamical problem and, by means of a numerical parametric analysis,
an equation to predict $\theta$ is developed. The equation is verified through
several numerical assessments in which the parameters are modified
simultaneously and arbitrarily. In addition, the qualitative influence of each
nondimensional parameter on the interface shape is reported.

# Parametric study of the interface behavior between two immiscible liquids
flowing through a porous medium

Alejandro David Mariotti  [inst1] Elena Brandaleze E-mail:
<EMAIL_ADDRESS>[inst2] Gustavo C. Buscaglia[inst3] E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(14 October 2009; 28 December 2009)

††volume: 1

99 inst1 Instituto Balseiro, 8400 San Carlos de Bariloche, Argentina. inst2
Departamento de Metalurgia, Universidad Tecnológica Nacional Facultad Regional
San Nicolás, 2900 San Nicolás, Argentina. inst3 Instituto de Ciências
Matemáticas e de Computação, Universidade de São Paulo, 13560-970 São Carlos,
Brasil.

##  1 Introduction

The fluid dynamics of the flow of two immiscible liquids through a porous
medium plays a key role in several engineering processes. Usually, though the
interest is focused on the extraction of one of the liquids, the simultaneous
extraction of both liquids is necessary. This is the case of oil production
and of ironmaking. The water injection method used in oil production consists
of injecting water back into the reservoir, usually to increase pressure and
thereby stimulate production. Normally, just a small percentage of the oil in
a reservoir can be extracted, but water injection increases that percentage
and maintains the production rate of the reservoir over a longer period of
time. The water displaces the oil from the reservoir and pushes it towards an
oil production well [1]. In the steel industry, this multiphase phenomenon
occurs inside the blast furnace hearth, in which the porous medium consists of
coke particles. The slag and pig iron are stratified in the hearth and,
periodically, they are drained through a lateral orifice. The understanding of
this flow is crucial for the proper design and management of the blast furnace
hearth [2]. In both examples above, when the liquids are drained, a complex
flow takes place in which the interface between the liquids moves, tilts and
bends.

Numerical simulation of multiphase flows in porous media is focused mainly in
upscaling methods, aimed at solving for large scale features of interest in
such a way as to model the effect of the small scale features [3–5]. Other
authors [6–8] use the numerical methods to model the complex multiphase flow
that takes place at the pore scale.

In this work, we numerically study the macroscopic behavior of the interface
between two immiscible liquids flowing through a porous medium when they are
drained through an opening. The effect of gravity on this phenomenon is
considered. We define four nondimensional parameters that rule the fluid
dynamical problem and, by means of a numerical parametric analysis, an
equation to predict the interface tilt in the vicinity of the orifice
($\theta$) is developed. The equation is verified through several numerical
cases where the parameters are varied simultaneously and arbitrarily. In
addition, the qualitative influence of each non-dimensional parameter on the
interface shape is reported.

##  2 Parametric Study

The numerical studies in this work were carried out by means of the program
FLUENT 6.3.26. Different models to simulate the two-dimensional parametric
study were used. The volume of fluid (VOF) method was chosen to treat the
interface problem [9]. The drag force in the porous medium was modeled by
means of the source term suggested by Forchheimer [10]. The source term for
the $i^{th}$ momentum equation is:

$\displaystyle S_{i}=-\left(\frac{\mu}{\alpha}V_{i}+\frac{1}{2}\rho
C|\overrightarrow{V}|V_{i}\right).$ (1)

For the constants $\alpha$ and $C$ in Eq. (1), we use the values proposed by
Ergun [10]:

$\displaystyle\alpha=\frac{\varepsilon^{3}d^{2}}{150(1-\varepsilon)^{2}},$ (2)

$\displaystyle C=1.75\frac{(1-\varepsilon)}{\varepsilon^{3}d},$ (3)

where $\varepsilon$ is the porosity, $d$ is the particle equivalent diameter,
$\rho$ is the density, $V$ is the velocity and $\mu$ is the dynamic molecular
viscosity.

Considering that the subscript 1 and 2 represent the fluid 1 and the fluid 2
respectively, three nondimensional parameters were considered in the
parametric study: viscosity ratio, $\mu_{R}=\mu_{1}/\mu_{2}$, density ratio,
$\rho_{R}=\rho_{1}/\rho_{2}$, and nondimensional velocity,
$V_{R}=V_{0}\rho_{2}L/\mu_{2}$; where $V_{0}$ is the outlet velocity and $L$ a
reference length.

###  2.1 Domain description

Figure 1: Sketch of the numerical 2D domain.

The numerical domain considered to carry out the parametric study was a two-
dimensional one composed by the porous medium sub-domain and the outlet sub-
domain. The porous sub-domain is a rectangle $10$m wide and $10$m tall. Inside
of it, a rigid, isotropic and homogeneous porous medium was arranged. We use a
porosity and particle diameter of $0.32$ and $0.006$m, respectively.

For the outlet domain we use a rectangle $0.02m$ wide and with a height
$L=0.01$m divided into two equal parts and located at the center of one of the
lateral edges. The part located at the end of the outlet domain is used to
impose the outlet velocity. Figure 1 shows a complete description of the
domain.

A quadrilateral mesh with $2.2\times 10^{4}$ cells was used, where the outlet
sub-domain mesh consists of $200$ elements in all the cases studied.

As boundary conditions, on edge 1 we define a zero gauge pressure condition
normal to the boundary and impose that only the fluid 1 can enter to the
domain through it. On edge 2 the boundary condition is the same as on edge 1
but the fluid consider in this case is fluid 2. On edge 7 we impose a zero
gauge pressure normal to the boundary but in this case the fluids can only
leave the domain. On the other edges (edges 4, 5, 6, and 8) we impose a wall
condition where the normal and tangential velocity is zero except for edge 3,
at which the tangential velocity is free and the stress tangential to the edge
is zero.

###  2.2 Interface evolution

To illustrate how an interface reaches the stationary position from an
initially horizontal one, three sets of curves were obtained.

Figure 2: Interface evolution when the initial position is below the outlet
level, without gravity.

Figure 2 shows the interface evolution for the case without the gravity effect
and the interface initial position is below the outlet level. The interface
modifies its tilt to reach the exit and it changes its shape to reach the
stationary profile.

Figures 3 and 4 show the interface evolution when the gravity is present but
the interface initial position is below and above the outlet level
respectively.

Figure 3: Interface evolution when the initial position is below the outlet,
with gravity. Figure 4: Interface evolution when the initial position is above
the outlet, with gravity.

###  2.3 Viscosity effect

One of the most important parameters to modify is the dynamical viscosity of
fluid 1. We maintain the properties of the fluid 2 as the properties of water
(density $998$Kg/m3, and dynamical viscosity $0.001$ Pa.s) and the density of
fluid 1 as the density of the oil ($850$ Kg/m3). The dynamical viscosity of
fluid 1 was varied from values smaller than those of fluid 2, to values much
greater.

Figure 5: Stationary interface profiles modifying the fluid 1 viscosity
without the gravity effect.

Two sets of curves were obtained, one considering the effect of gravity and
the other without considering it. Figure 5 shows the stationary interface
profiles for the different values of viscosity, without gravity. A value of
$V_{R}=1.5\times 10^{4}$ and $\rho_{R}=1.17$ were chosen. It is possible to
observe that, when fluid 1 has a viscosity higher than that of fluid 2, the
interface profile is above the outlet and points downwards at the outlet. If
fluid 1 has a lower viscosity, the opposite happens.

Figure 6: Stationary interface profiles modifying the fluid 1 viscosity with
the gravity effect.

When considering gravity, the value of $V_{R}$ was changed to $1\times 10^{5}$
($V_{0}=10$m/s), since for smaller values the interface may not reach the
outlet (this is later studied in Fig. 10). Figure 6 shows the curves obtained
for this situation, where the interface only lies over the outlet level for
the higher $\mu_{R}$ values.

###  2.4 Outlet velocity effect

$V_{0}$ is varied from a small value, similar to the porous medium velocity
($V_{0}=0.2$m/s or $V_{R}=2000$), to a very large one ($V_{0}=50$m/s or
$V_{R}=5\times 105$). Maintaining the properties of fluid 2 similar to those
of water, two sets of curves were obtained ($\mu_{R}>1$ and $\mu_{R}<1$),
shown in Figs. 7 and 8, respectively.

Figure 7: Stationary interface profiles for several values of $V_{R}$, without
gravity, for $\mu_{R}>1$ ($\mu_{R}=35$).

When the effect of gravity was considered, two additional sets of curves
(Figs. 9 and 10) were obtained.

Figure 7 shows the effect of $V_{R}$ when the viscosity of fluid 1 is greater
than that of fluid 2, without gravity. It is possible to see that, as $V_{R}$
increases, the interface tilt at the outlet is maximal for $V_{R}=1\times
10^{5}$.

On the other hand, Fig. 8 shows the interface profiles when the viscosity of
fluid 1 is smaller than that of fluid 2. We observe that as $V_{R}$ increases
the interface tends to the horizontal position.

Figure 8: Stationary interface profiles for several values of $V_{R}$, without
gravity, for $\mu_{R}<1$ ($\mu_{R}=0.01$).

Figure 9 shows the different stationary interface positions when the gravity
effect is present for $\mu_{R}>1$. The effect of gravity is quite significant,
the interface ascends but only for the highest value of $V_{R}$ it lies above
the outlet level.

Figure 9: Stationary interface profiles for several values of $V_{R}$, with
gravity, for $\mu_{R}>1$ ($\mu_{R}=35$).

Figure 10 shows the curves when the viscosity of fluid 1 is lower than that of
fluid 2 ($\mu_{R}<1$). The behavior is different from that without gravity. In
fact, there exists a minimum outlet velocity below which the interface does
not reach the outlet.

Figure 10: Stationary interface profiles for several values of $V_{R}$, with
gravity, for $\mu_{R}<1$ ($\mu_{R}=0.01$).

###  2.5 Density effect

The effect of the density ratio on the interface profile was studied in the
presence of gravity. Keeping fluid 2 with the properties of water and the
viscosity of fluid 1 as $0.035$Pa.s ($\mu_{R}=35$), the density of fluid 1 was
varied from its original value to one three times smaller than that of fluid
2. In Fig. 11 it is seen that as $\rho_{R}$ increases, the interface profile
ascends significantly, with a less significant change in the tilt angle at the
outlet.

Figure 11: Stationary interface profiles for several values of the density of
fluid 1, with $V_{R}=1.5^{4}$ and $\mu_{R}=35$.

##  3 Generic expression

From the study on the influence of each nondimensional parameter on the
interface behavior, an equation that predicts the interface angle at the
immediate vicinity of the outlet ($\theta$) was crafted. For practical
reasons, the cases where gravity is present were considered to develop the
equation.

In Sect. 2.2, it is possible to see that when the nondimensional parameters
$\rho_{R}$, $\mu_{R}$ and $V_{R}$ are constant the interface changes its shape
until it reaches a stationary profile.

For this reason, a fourth nondimensional parameter is considered, the volume
fraction of fluid 1 in the outlet flow (VF).

A generic expression [(Eq. (4)], consisting of three terms and containing 22
constants, was adjusted by trial and error until satisfactory agreement with
the numerical results was found.

$\displaystyle\theta$ $\displaystyle=\alpha\mu_{R}^{b}V_{R}^{c}\rho_{R}^{d}$
$\displaystyle+e\mu_{R}^{f}V_{R}^{g}\rho_{R}^{h}\exp(-i\mu_{R}^{j}V_{R}^{k}\rho_{R}^{l}VF^{m})$
$\displaystyle+n\mu_{R}^{o}V_{R}^{p}\rho_{R}^{q}\exp(-r\mu_{R}^{s}V_{R}^{t}\rho_{R}^{u}VF^{v})$
(4)

Table 1 shows the values of the constants in the generic expression.

a | -29.1 | i | $1.162\times 10^{7}$ | p | 0.1
---|---|---|---|---|---
b | -0.04 | j | -0.18 | q | 0.72
c | 0.1 | k | -1.64 | r | 2763.1
d | 0.45 | l | -1 | s | 0.4
e | 206 | m | 0.63 | t | -0.6
f | 0.035 | n | 12.74 | u | -1.82
g | -0.05 | o | 0.085 | v | 3.2
h | -1.26 |  |  |  |
Table 1: Constant values in the generic expression.

###  3.1 Equation verification

To verify that the generic expression (4) predicts the value of $\theta$
correctly when the parameters are arbitrarily modified, 21 additional
numerical cases were simulated. These cases cover a wide range of physical
properties of the liquids and of the characteristics of the porous medium (by
means of the coefficients $1/\alpha$ and $C$).

The interface angle obtained from the generic expression ($\theta_{GE}$) was
compared with the interface angle obtained from the simulations
($\theta_{S}$). Table 2 shows the five porous medium types (PT) that were
chosen.

PT | $D$ | $\varepsilon$ | $1/\alpha$ | $C$ | Resistance
---|---|---|---|---|---
A | 0.005 | 0.3 | $10.88\times 10^{7}$ | $1.81\times 10^{4}$ | Very high
B | 0.006 | 0.32 | $5.88\times 10^{7}$ | $1.21\times 10^{4}$ | High
C | 0.02 | 0.2 | $3\times 10^{7}$ | $1.75\times 10^{4}$ | Medium
D | 0.02 | 0.25 | $1.35\times 10^{7}$ | 8400 | Low
E | 0.05 | 0.17 | $8.41\times 10^{6}$ | $1.18\times 10^{4}$ | Very low
Table 2: Porous medium types.

Some cases (1, 2, 4, 5, 9, 11, 17-21) were chosen based on the possible
combinations of immiscible liquids that can be manipulated in real situations.
For the remaining cases, the properties of the liquids were fixed at arbitrary
values (fictitious liquids) so that a wide range of the nondimensional
parameters was covered. Table 3 shows the description of each numerical case,
while Table 4 shows the corresponding nondimensional parameter values and PT.

Case |  Fluid 1 |  Fluid 2 | $\mu_{1}$ | $\mu_{2}$ | $\rho_{1}$ | $\rho_{2}$
---|---|---|---|---|---|---
1 |  Heavy oil |  Water solution | 0.4 | 0.005 | 850 | 998
2 |  Light oil |  Water emulsion | 0.012 | 0.06 | 850 | 998
3 |  – |  – | 0.08 | 0.008 | 4000 | 4680
4 |  Kero-sene |  Water | $24\times 10^{-4}$ | 0.001 | 780 | 998
5 |  Ace-tone |  Water | $3.3\times 10^{-4}$ | 0.001 | 791 | 998
6 |  – |  – | 0.003 | 0.01 | 400 | 720
7 |  – |  – | 0.2 | 0.01 | 1500 | 2700
8 |  – |  – | 0.3 | 0.004 | 3300 | 5940
9 |  Light slag |  Hot pig iron | 0.02 | 0.001 | 2800 | 7000
10 |  – |  – | 0.5 | 0.013 | 500 | 1250
11 |  Medium |  pig | 0.4 | 0.005 | 2800 | 7000
|  slag |  iron |  |  |  |
12-16 |  – |  – | 0.08 | 0.008 | 4000 | 4680
17-21 |  Heavy slag |  pig iron | 0.4 | 0.005 | 2800 | 7000
Table 3: Cases description. Case | PT | $\rho_{R}$ | $\mu_{R}$ | $V_{R}$ | VF
---|---|---|---|---|---
1 | B | 1.17 | 80 | $5\times 10^{4}$ | 2.8
2 | B | 1.17 | 0.2 | $5\times 10^{4}$ | 87.2
3 | B | 1.17 | 10 | $10\times 10^{4}$ | 28.4
4 | B | 1.28 | 2.4 | $5\times 10^{4}$ | 96.1
5 | B | 1.26 | 0.33 | $1\times 10^{5}$ | 96.8
6 | B | 1.8 | 0.3 | $1\times 10^{5}$ | 93.2
7 | B | 1.8 | 20 | $1\times 10^{5}$ | 16.1
8 | B | 1.8 | 80 | $8\times 10^{4}$ | 18.4
9 | B | 2.5 | 20 | $1\times 10^{5}$ | 100.0
10 | B | 2.5 | 40 | $1\times 10^{5}$ | 5.5
11 | B | 2.5 | 80 | $5\times 10^{4}$ | 70.8
12 | A | 1.2 | 10.0 | $1\times 10^{5}$ | 23.1
13 | B | 1.2 | 10.0 | $1\times 10^{5}$ | 28.4
14 | C | 1.2 | 10.0 | $1\times 10^{5}$ | 41.5
15 | D | 1.2 | 10.0 | $1\times 10^{5}$ | 53.4
16 | E | 1.2 | 10.0 | $1\times 10^{5}$ | 63.7
17 | A | 2.5 | 80.0 | $5\times 10^{4}$ | 15.8
18 | B | 2.5 | 80.0 | $5\times 10^{4}$ | 24.3
19 | C | 2.5 | 80.0 | $5\times 10^{4}$ | 43.2
20 | D | 2.5 | 80.0 | $5\times 10^{4}$ | 70.8
21 | E | 2.5 | 80.0 | $5\times 10^{4}$ | 94.0
Table 4: Parameter values and PT for all cases described in Table 3.

We define an error ($e=100|\Delta\theta|/180$) as the percentage of the
absolute value of the difference between the interface angles
($\Delta\theta=\theta_{S}-\theta_{GE}$) divided by the interface angle range
($180^{\circ}$). Figure 12 shows the comparison between the generic expression
and the numerical cases. It is seen that the generic expression (4) predicts
the interface angle, for the cases used in this study, with an error smaller
than 10%.

Figure 12: Comparison between the predictions of the generic expression and
the numerical result for the 21 validation cases.

##  4 Conclusions

A numerical study of the macroscopic interface behavior between two immiscible
liquids flowing through a porous medium, when they are drained through an
opening, has been reported. Four nondimensional parameters that rule the
fluid-dynamical problem were identified. Thereby, a numerical parametric
analysis was developed where the qualitative observation of the resulting
interface profiles contributes to the understanding of the effect of each
parameter. In addition, a generic expression to predict the interface angle in
the immediate vicinity of the outlet opening ($\theta$) was developed. To
verify that the generic equation predicts the value of $\theta$ correctly,
$21$ numerical cases with widely different parameters were simulated.
Considering that the cases encompass a large class of liquids and porous
media, the prediction of $\theta$ within an error of 10% is considered
satisfactory.

###### Acknowledgements.

A. D. M. and E. B. are grateful for the support from Metallurgical Department
and DEYTEMA (UTNFSRN). G. C. B. acknowledges partial financial support from
CNPq and FAPESP (Brazil).

## References

  * [1] W C Lyons, G J Plisga, Standard Handbook of Petroleum & Natural Gas Engineering \- 2nd ed, Gulf Professional Publishing, Burlington (2005).
  * [2] A K Biswas, Principles of blast furnace ironmaking: theory and practice, Cootha Publishing House, Brisbane (1981).
  * [3] A Westhead, Upscaling for two-phase flows in porous media, PhD thesis: California Institute of Technology, Pasadena, California (2005).
  * [4] R E Ewing, The Mathematics of reservoir simulation, SIAM, Philadelphia (1983).
  * [5] M A Cardoso, L J Durlofsky, Linearized reduced-order models for subsurface flow simulation, J. Comput. Phys. 229, 681 (2010).
  * [6] M J Blunt, Flow in porous media - pore-network models and multiphase flow, Curr. Opin. Colloid Interface Sci. 6, 197 (2001).
  * [7] Z Chen, G Huan, Y Ma, Computational methods for multiphase flows in porous media, SIAM, Philadelphia (2006).
  * [8] Y Efendiev, T Houb, Multiscale finite element methods for porous media flows and their applications, Appl. Num. Math. 57, 577 (2007).
  * [9] FLUENT 6.3 User’s Guide, Fluent Inc. (2006).
  * [10] J Bear, Dynamics of fluids in porous media, Dover Publications Inc., New York (1988).


# Combinatorial Bandits under Strategic Manipulations

Jing Dong<EMAIL_ADDRESS>The Chinese University of Hong Kong,
Shenzhen ,  Ke Li<EMAIL_ADDRESS>The Chinese University of Hong Kong,
Shenzhen ,  Shuai Li<EMAIL_ADDRESS>Shanghai Jiao Tong University and
Baoxiang Wang<EMAIL_ADDRESS>The Chinese University of Hong Kong,
Shenzhen

(2021)

###### Abstract.

Strategic behavior against sequential learning methods, such as “click
framing” in real recommendation systems, have been widely observed. Motivated
by such behavior we study the problem of combinatorial multi-armed bandits
(CMAB) under strategic manipulations of rewards, where each arm can modify the
emitted reward signals for its own interest. This characterization of the
adversarial behavior is a relaxation of previously well-studied settings such
as adversarial attacks and adversarial corruption. We propose a strategic
variant of the combinatorial UCB algorithm, which has a regret of at most
$O(m\log T+mB_{max})$ under strategic manipulations, where $T$ is the time
horizon, $m$ is the number of arms, and $B_{max}$ is the maximum budget of an
arm. We provide lower bounds on the budget for arms to incur certain regret of
the bandit algorithm. Extensive experiments on online worker selection for
crowdsourcing systems, online influence maximization and online
recommendations with both synthetic and real datasets corroborate our
theoretical findings on robustness and regret bounds, in a variety of regimes
of manipulation budgets.

multi-armed bandits, strategic manipulations, crowdsourcing, online
information maximization, recommendation systems

††copyright: acmcopyright††journalyear: 2021††copyright: none††conference: The
fifteenth ACM International Conference on Web Search and Data Mining (WSDM
’22); February 21–25, 2022; Phoenix, Arizona††booktitle: The fifteenth ACM
International Conference on Web Search and Data Mining (WSDM ’22), February
21–25, 2022, Phoenix, Arizona††ccs: Computing methodologies Online learning
settings††ccs: Information systems Crowdsourcing††ccs: Information systems
Social networks††ccs: Computing methodologies Sequential decision making

##  1\. Introduction

Sequential learning methods feature prominently in a range of real
applications such as online recommendation systems, crowdsourcing systems, and
online influence maximization problems. Among those methods, the multi-armed
bandits problem serves as a fundamental framework. Its simple yet powerful
model characterizes the dilemma of exploration and exploitation which is
critical to the understanding of online sequential learning problems and their
applications (Thompson, 1933; Robbins, 1952; Auer et al., 2002a; Lattimore and
Szepesvári, 2020). The model describes an iterative game constituted by a
bandit algorithm and many arms. The bandit algorithm is required to, through a
horizon $T$, choose an arm to pull at each time step. As the objective is to
maximize the cumulative reward over time, the algorithm balances between
exploiting immediate rewards based on the information collected or pulling
less explored arms to gain more information about arms (Anantharam et al.,
1987; Auer et al., 2002b; Cesa-Bianchi and Lugosi, 2006).

Out of the real applications, many motivate the extension of MAB towards
combinatorial multi-armed bandits (CMAB), where multiple arms can be selected
in each round (Chen et al., 2013; Combes et al., 2015; Li et al., 2016;
Zimmert et al., 2019; Rejwan and Mansour, 2020). CMAB demonstrates its
effectiveness on problems like online social influence maximization, viral
marketing, and advertisement placement, within which many offline variants are
NP-hard. However, existing MAB and CMAB algorithms are often developed either
under benign assumptions on the arms (Chen et al., 2013; Kveton et al., 2015;
Wei and Luo, 2018) or purely adversarial arms (Auer et al., 2002c). In the
former setting, the arms are commonly assumed to report their reward signals
truthfully without any strategic behavior, under which the drawbacks are
apparent. In the latter setting, arms can attack any deployed algorithm to
regret of $O(T)$ with this capability of reward manipulations, which is
catastrophic for a bandit algorithm. This assumption is stringent and rarely
realistic.

In this paper, we adapt the combinatorial UCB (CUCB) algorithm with a
carefully designed UCB-based exploration term. A major difficulty stems from
not knowing the manipulation term made by the arms, while our algorithm
overcomes this by depending only on the knowledge of the maximum possible
strategic budget. Previous results by (Feng et al., 2020) only implies
robustness of UCB style algorithm under stochastic multi armed bandits setting
under only full knowledge of step wise deployment of strategic budget. New
tail bounds over the proposed exploration term and a new trade-off parameter
that balances exploration and exploitation are utilized to facilitate the
analysis of our algorithm. We further establish results on the robustness of
our UCB variant under strategic arms with an algorithm-dependent budget lower
bound.

Our proposed algorithms are also evaluated empirically through an extensive
set of synthetic environments and real datasets. The real applications include
reliable workers selection in online crowdsourcing systems, where workers
might misrepresent a result for a better chance to be selected in the future;
online information maximization, where nodes modify the spread to include
itself into the seed set; and online recommendation systems, which
characterizes the “click framing” behavior. Through a wide range of tasks and
parameters, the experiment results corroborate our theoretical findings and
demonstrate the effectiveness of our algorithms.

###  1.1. Motivating Examples

The setting of strategic manipulations describes the strategic behavior found
in a variety of real applications. Consider a crowdsourcing platform that
provides a data labeling service for payment. The platform interacts with a
group of customers and a pool of workers. The customers request tasks to the
platform for labeling and the platform is then responsible for selecting
workers from the worker pool to complete the tasks. This process repeats,
during which the platform learns the best deployment. We maintain a mild
assumption that the payments from customers are non-decreasing with the
quality of labels. To maximize its profit, it is desired for the platform to
select workers that provides the most reliable labels. The workflow of the
platform can be described in the diagram below.

While the platform and the customers desire quality labels, it may not
entirely be in the worker’s interest to exert the highest effort and thus
report quality labels each time, which factors into a range of reasons.
Workers may adapt strategic behaviors to maximize their own utility instead.
Thus, it becomes crucial to identify reliable workers to prevent strategic
behaviors that jeopardize profits. This naturally translates to a multi-armed
bandits problem under strategic manipulations where the workers are the
strategic arm and the payments act as the rewards. Under ideal assumptions it
had shown the effectiveness of bandits algorithms on such problems (Jain et
al., 2014; Tran-Thanh et al., 2014; Rangi and Franceschetti, 2018).

Figure 1. Online crowdsourcing system

##  2\. Related Work

The problem of multi-armed bandits (MAB) was first investigated back in 1952
while some techniques utilized were developed back in 1933 (Thompson, 1933;
Robbins, 1952; Berry and Fristedt, 1985; Auer et al., 2002a; Lattimore and
Szepesvári, 2020). Since then it has been extensively explored and serves as
the foundation of many modern areas, including reinforcement learning,
recommendation systems, graph algorithms, etc. (Bouneffouf et al., 2021;
Vaswani et al., 2017; Durand et al., 2018; Li et al., 2019, 2020a). With the
need to model the selection of multiple arms in one round, MAB is then
extended to combinatorial multi-armed bandits (CMAB), which see many
deployments in real applications like news/goods recommendation, medical
trials, routing, and so forth (Wang et al., 2017; Talebi et al., 2018;
Sankararaman and Slivkins, 2018; Li et al., 2020b).

Real applications motivate the community to derive algorithms in more adaptive
environments. The first of which considers adversarial bandits with the
classic EXP3 algorithm. The arms are assumed to be non-stationary but non-
adaptive (which means that algorithms will adapt to the adversarial) (Auer et
al., 2002c). Despite that adversarial bandits do not fall into the scale of
this paper’s related work, it leads tremendous effort to the following topics
in adaptive arms.

#### Adversarial corruptions

The adversary is given the ability to replace the observations of the bandit
algorithm with arbitrary values within some constraints. Gupta et al. (2019)
discuss the constraint that rewards are modified for at most $T_{0}$ rounds
out of the total $T$ rounds. The asymptotic regret bound $O(mT_{0})$ achieved
in the work is shown to match the negative result, where $m$ is the number of
arms. Lykouris et al. (2018) discussed a different constraint where the
corruption $z_{t}$ at time $t$ is cumulative up to some constant $B$. The
regret achieved under this constrained corruption is bounded by
$O(mB\log(\frac{mT}{\delta}))$ with probability at least $1-\delta$.
Altschuler et al. (2019) restricts corruptions as independent Bernoulli events
with probability $b$, while if corruption happens the reward becomes arbitrary
and adversarial. This problem is addressed with median statistics with gap-
dependent matching regret upper and lower bounds of $O(\sum_{i\neq
i^{\ast}}\frac{1}{\Delta_{i}}\log(\frac{K}{\Delta_{i}}))$, where $i^{\ast}$
denotes the optimal arm and $\Delta_{i}$ is the suboptimality of arm $i$.

Several lines of research also discuss corruption topics in frequentist
inference and partial monitoring (Gajane et al., 2018), best arm
identification (Gupta et al., 2019), and adversarial bandits (Yang et al.,
2020).

#### Adversarial attacks

Different from arms in adversarial corruptions who intend to maximize the
regret of the bandit algorithm, arms in the adversarial attack setting have
the goal to maximize their number of pulls. The setting is first considered by
Jun et al. (2018), where it shows that the attacker may spend a budget of
$O(\log T)$ to deceit UCB and $\epsilon$-greedy algorithms to pull the target
arms for at least $T-o(T)$ times. Stochastic and contextual MAB algorithms
also suffer from undesired loss from this adversarial attack, under a variety
of attack strategies (Liu and Shroff, 2019). Linear MAB algorithms, however,
are shown to be near-optimal up to some linear or quadratic terms on the
attack budget $B$ (Garcelon et al., 2020; Bogunovic et al., 2020).

#### Strategic manipulations

The setting of strategic manipulations further weakens the capability of the
adaptive arms and prevents the bandit algorithms from being overcautious. The
objective of an arm is still utility maximization under strategic
manipulations, while each arm works on its utility individually. Instead of
having a global coordinator for the adversarial attack strategy, the strategic
arms seek the best response via the dominant Nash equilibrium. The strategic
manipulation setting is first studied by Braverman et al. (2019) where each
arm is assumed to keep a portion of the reward in each round and arms maximize
the cumulative reward it keeps. The performance of bandit algorithms will then
be catastrophic under the dominant Nash equilibrium, receiving an expected
cumulative reward of $0$ almost surely. With the utility of maximizing the
number of pulls for each strategic arm, common bandits algorithms are proved
to be robust with guaranteed $O(\log T)$ regret bound, but only under constant
strategic budgets (Feng et al., 2020). For $\omega(\log T)$ budgets, bandits
under strategic manipulations remain an open problem and will be discussed in
this paper.

##  3\. Problem Formulation

We consider the problem of combinatorial multi-armed bandits (CMAB) under the
setting of strategic arms. In strategic CMAB, each arm is given a budget and
the arm can strategically increase its emitted reward signals cumulatively up
to this budget _for its own interest_. This problem is a Stackelberg game that
involves two parties. The bandit learning algorithm is deployed first to
maximize its cumulative reward under the best response of the followers. The
$m$ strategic bandits arms then deplete their budget where each of them aims
to maximize its expected number of pulls. Knowing the principal’s strategy and
other followers’ budget information, the followers are assumed to place their
strategies according to the dominant Nash equilibrium between them.

Formally, given a time horizon $T$, the the bandit learning algorithm is asked
to pull a subset of arms, denoted by an arm subset $S_{t}\in\mathcal{S}$ at
each time $t\in[T]$, where $\mathcal{S}={\\{0,1\\}^{m}}$ is the set of all
possible arm subsets. At the time $t$, based on the principal’s choice of arm
subset, stochastic rewards $x_{i,t}$ are generated by arm $i$ from the
underlying $1$-sub-Gaussian distribution with mean $\mu_{i}$, independent of
other arms in $S_{t}$. The principal does not observe these rewards. Instead,
each arm can increase the emitted reward signal by an arbitrary amount
$z_{i,t}\geq 0$, as long as the cumulative manipulation over the horizon does
not exceed a given budget $B_{i}$. The principal then receives the semi-bandit
feedback $\\{x_{i,t}+z_{i,t}\\}_{i\in S_{t}}$.

Let $\bm{\mu}=(\mu_{1},\mu_{2},...,\mu_{i})$ be the vector of expectations of
all arms. The expected reward of playing any arm subset S in any round
$r_{\bm{\mu}}(S)=\mathbb{E}[R_{t}(S)]$,which is a function of arm subset $S$
and $\bm{\mu}$. The reward function $r_{\bm{\mu}}(S)$ is assumed to satisfy
two axioms:

  * •

Monotonicity. The expected reward of playing any arm subset $S\in\mathcal{S}$
is monotonically non-decreasing with respect to the expected reward vector.
That is, if for all $i\in[m],\mu_{i}\leq\mu_{i}^{\prime}$, then
$r_{\bm{\mu}}(S)\leq r_{\bm{\mu}^{\prime}}(S)$.

  * •

Bounded smoothness. There exists a strictly increasing function $f(\cdot)$,
termed the bounded smoothness function, such that for any two expected reward
vectors $\bm{\mu}$ and $\bm{\mu^{\prime}}$ satisfying
$\|\bm{\mu}-\bm{\mu^{\prime}}\|_{\infty}\leq\Lambda$, we have
$|r_{\bm{\mu}}-r_{\bm{\mu^{\prime}}}|\leq f({\Lambda})$.

These axioms cover a rich set of reward functions and the explicit forms of
$R_{t}(S)$ and $r_{\bm{\mu}}(S)$ are not needed to be specified (Chen et al.,
2013).

Without loss of generality, assume that
$S^{\ast}=\operatorname*{arg\,max}_{S\subseteq\mathcal{S}}r_{\bm{\mu}}(S)$ is
the unique optimal subset of arms. When placing reward manipulations, each
strategic arm has access to its own history
$h_{i,t}=\\{I_{i,t^{\prime}},x_{i,t^{\prime}},z_{i,t^{\prime}}\\}_{t^{\prime}\geq
1}$, where $I_{i,t^{\prime}}$ is the indicator of whether arm $i$ is pulled at
time $t^{\prime}$ and $t^{\prime}<t$. The strategy of arm $i$ is determined by
a function that maps this history to a manipulation $z_{i,t}$, as
$Z_{i,t}\colon h_{i,t-1}\to\mathbb{R}$. Without loss of generality, we assume
that arms in the optimal arm subset $i\in S^{\ast}$ have strategic budgets of
$0$, which restricts their $z_{i,t}$ to be $0$.

In the combinatorial setting, even with the exact reward vector $\bm{\mu}$
provided, it can be hard to exactly compute the optimized $r_{\bm{\mu}}(S)$.
In view of this, many have studied probabilistic approximation algorithms in
combinatorial problems, which indicates that an ($\alpha,\beta$)-approximation
oracle defined below can be usually available.

###### Definition 1 (Approximation oracle).

Let $0\leq\alpha,\beta\leq 1$ and define
${OPT}_{\bm{\mu}}=\max_{S\in\mathcal{S}}r_{\bm{\mu}}(S)$. An oracle is called
an ($\alpha,\beta$)-approximation oracle if it takes an expected reward vector
$\bm{\mu}$ as input and outputs an arm subset $S\in\mathcal{S}$ such that
$\mathbb{P}(r_{\bm{\mu}}(S)\geq\alpha\cdot{OPT}_{\bm{\mu}})\geq\beta$. That
is, the oracle gives an arm subset $S$ that is at least as good as $\alpha$
times the reward of an optimal arm subset with probability at least $\beta$.

Denote
${S_{B}}=\\{r_{\bm{\mu}}(S)<\alpha\cdot{OPT}_{\bm{\mu}}|S\in\mathcal{S}\\}$ to
be the set of suboptimal arm subsets under the approximation oracle. Note that
a suboptimal arm subset can be given by the oracle for two reasons. The
($\alpha,\beta$)-approximation oracle can fail, which happens with probability
at most $1-\beta$. The estimation of $\bm{\mu}$ can deviate from the true
value by a significant amount, resulting in accurate input to the oracle.

The objective of the principal is to maximize the expected cumulative reward
before manipulation over the time horizon $T$. Equivalently, the principal
minimizes the regret, the cumulative difference between the scaled optimal
reward and expected actual reward, as defined below.

###### Definition 2 (Regret).

With access to an ($\alpha,\beta$)-approximation oracle, the regret of a
combinatorial bandit algorithm for $T$ rounds is

$Regret_{\bm{\mu},\alpha,\beta}(T)=T\cdot\alpha\cdot\beta\cdot{OPT}_{\bm{\mu}}-\mathbb{E}\big{[}\sum^{T}_{t=1}r_{\bm{\mu}}(S_{t})\big{]}\,,$

where the randomness in $\mathbb{E}[\sum^{T}_{t=1}r_{\bm{\mu}}(S_{t})]$
involves the stochasticity of the bandit algorithm and the oracle.

The objective of each strategic arm $i\in[m]\setminus S^{\ast}$, however, is
to maximize the number $\sum_{t=1}^{T}I_{i,t}$ of times it is pulled over the
time horizon. To achieve this, the arm needs to confuse the principal by
deviating the emitted reward signals up to the possessed budget.

##  4\. Strategic Combinatorial UCB

We now propose a variant of combinatorial upper confidence bound algorithm
that is robust to strategic manipulations of rewards in Algorithm 1. The only
mild assumption we maintain is that the learning algorithm has the knowledge
of the largest budget possessed among all bandits arms, i.e, $B_{max}$. This
is a relaxation of the assumptions made by Feng et al. (2020) on the strategic
UCB algorithm, in which the learning algorithm has access to the cumulative
use of budget at every time step. We start with a detailed description of the
algorithm and then analyze the theoretical upper bound of regret, which enjoys
$O(m\log{T}+mB_{max})$.

For each arm $i$, our algorithm maintains a counter $K_{i,t-1}$ as the total
number of times arm $i$ has been pulled up to time $t-1$ and
$\widetilde{\mu}_{i,t}=\frac{\sum_{j=1}^{t-1}(x_{i,j}+z_{i,j})}{K_{i,t-1}}$ as
the empirical mean estimation based on the observations. At each time step,
the algorithm computes the UCB estimation
$\bar{\mu}_{i,t}=\widetilde{\mu}_{i,t}+\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{B_{max}}{K_{i,t-1}}$
for $i\in[m]$. With $\bar{\mu}_{i,t}$, the $(\alpha,\beta)$-approximation
oracle then outputs an approximately optimal arm subset $S_{t}\in\mathcal{S}$.
The algorithm plays the return arm subset and update the counter $K_{i,t}$ and
the estimation $\widetilde{\mu}_{i,t}$ accordingly.

1 Input: Horizon $T$, number $m$ of arms, maximum budget $B_{max}$

2 Output: Arm subset $S_{t}$

3 Initialize $K_{i,0}=0$ and $\widetilde{\mu}_{i,0}=0$ for $i\in[m]$

4 for  _t = 1 $\to$ m_ do

5 Play an arbitrary arm subset $S_{t}\in\mathcal{S}$ such that $t\in S_{t}$

6 $K_{i,t}=K_{i,t-1}+1$ for $i\in S_{t}$

7 $\widetilde{\mu}_{j}=x_{i,t}+z_{i,t}$ for $i\in S_{t}$

8for  _t = m+1 $\to$ T_ do

9 For $i\in[m]$, compute
$\bar{\mu}_{i,t}=\widetilde{\mu}_{i,t-1}+\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{B_{max}}{K_{i,t-1}}$

10 $S_{t}$ = oracle$(\bar{\mu}_{1,t},\bar{\mu}_{2,t},.....,\bar{\mu}_{m,t})$

11 Play arm subset $S_{t}$ and update $K_{i,t}=K_{i,t-1}+1$ and
$\widetilde{\mu}_{i,t}=\frac{\sum_{j=1}^{t}(x_{i,j}+z_{i,j})}{K_{i,t}}$ for
$i\in S_{t}$

12

Algorithm 1 SCUCB

We first introduce a few notations that are used in our results. Define, for
any arm $i\in[m]$, the suboptimality gaps as

$\displaystyle\Delta^{i}_{min}=\alpha\cdot{OPT}_{\bm{\mu}}-\max\\{r_{\bm{\mu}}(S)\mid
S\in S_{B},i\in S\\}\,,$
$\displaystyle\Delta^{i}_{max}=\alpha\cdot{OPT}_{\bm{\mu}}-\min\\{r_{\bm{\mu}}(S)\mid
S\in S_{B},i\in S\\}\,.$

We then denote the maximum and minimum of the suboptimality gaps as
$\Delta_{max}=\max_{i\in[m]}\Delta^{i}_{max}$ and
$\Delta_{min}=\min_{i\in[m]}\Delta^{i}_{min}$.

The following lemma re-establish the canonical tail bound inequality in UCB
under the setting of strategic manipulations.

###### Lemma 1.

Let
${\Lambda}_{i,t}=\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{\rho_{i,t-1}}{K_{i,t-1}}$,
where $\rho_{i,t-1}$ is the total strategic budget spent by arm $i$ up to time
$t-1$ and $K_{i,t-1}$ be the total number of pulls of arm $i$ up to time
$t-1$. Define the event $E_{t}=\\{|\
\widetilde{\mu}_{i,t-1}-\mu_{i}|\leq\Lambda_{i,t},\forall i\in[m]\\}$, where
$\mu_{i}$ is the true mean of arm $i$’s underlying distribution. Then,
$\mathbb{P}(\lnot E_{t})\leq 2m\cdot t^{-2}$.

Armed with Lemma 1, we present one of our main theorems, Theorem 2, which
gives the regret bound of $O(\log T)$ of SCUCB. The outline of the proof
follows that of CUCB by Chen et al. (2013). To complete the proof, we
carefully choose $\psi_{t}$, which controls the trade-off between the
exploration and exploitation periods.

###### Theorem 2.

The regret of the SCUCB algorithm with $m$ strategic arms in time horizon $T$
using an $(\alpha,\beta)$-approximation oracle is at most

$\displaystyle
m\cdot\Delta_{max}\left(\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{T}}{\left(f^{-1}(\Delta_{min})\right)^{2}}+\frac{\pi^{2}}{3}+1\right)\,,$

where $f^{-1}(\cdot)$ is the inverse bounded smoothness function.

###### Proof sketch.

We introduce a counter $N_{i}$ for each arm $i\in[m]$ after the $m$-round
initialization and let $N_{i,t}$ be the value of $N_{i}$ at time $t$. We
initialize $N_{i,m}=1$. By definition, $\sum_{i\in[m]}N_{i,m}=m$. For $t>m$,
the counter $N_{i,t}$ is updated as follows:

  * •

If $S_{t}\in S_{B}$, then $N_{{i^{\prime}},t}=N_{{i^{\prime}},t-1}+1$ where
$i^{\prime}=$ $\operatorname*{arg\,min}_{i\in S_{t}}$ $N_{i,t-1}$. In the case
that $i^{\prime}$ is not unique, we break ties arbitrarily;

  * •

If $S_{t}\notin S_{B}$, then no counters will be updated.

As such, the total number of pulls of suboptimal arm subsets is less than or
equal to $\sum_{i=1}^{m}N_{i,T}$.

Define
$\psi_{t}=\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{t}}{\left(f^{-1}(\Delta_{min})\right)^{2}}>c$,
where $c$ is the larger solution of

$\displaystyle(f^{-1}(\Delta_{min}))^{2}c^{2}+16B_{max}^{2}-((8B_{max}f^{-1}(\Delta_{min})-6\log{t})c=0\,.$

Then, we decompose the total number $\sum_{i=1}^{m}N_{i,T}$ of pulls of
suboptimal arm subsets as

$\displaystyle\sum_{i=1}^{m}N_{i,T}=\ $ $\displaystyle
m+\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in S_{B}\\}$ $\displaystyle=\ $
$\displaystyle m+\sum_{t=m+1}^{T}\sum_{i=1}^{m}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t}>N_{i,t-1},N_{i,t-1}\leq\psi_{t}\\}$
$\displaystyle+\sum_{t=m+1}^{T}\sum_{i=1}^{m}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t}>N_{i,t-1},N_{i,t-1}>\psi_{t}\\}$ $\displaystyle\leq\ $
$\displaystyle m+m\psi_{T}+\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t-1}>\psi_{t},\forall i\in S_{t}\\}\,.$

The inequality follows as $\sum_{t=m+1}^{T}\sum_{i=1}^{m}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t}>N_{i,t-1},N_{i,t-1}\leq\psi_{t}\\}$ can be trivially bounded by
$m\psi_{T}$. Thus the key to bound the total number of pulls of suboptimal arm
subset is to upper bound $\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t-1}>\psi_{t},\forall i\in S_{t}\\}$. Let $F_{t}$ denotes the event
that the oracle fails to provide an $\alpha$-approximate arm subset with
respect to the input vector
$\bar{\bm{\mu}}=(\bar{\mu}_{1,t},\bar{\mu}_{2,t},.....,\bar{\mu}_{m,t})$. Then
we can decompose $\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t-1}>\psi_{t},\forall i\in S_{t}\\}$ as

$\displaystyle\quad\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t-1}>\psi_{t},\forall i\in S_{t}\\}$
$\displaystyle\leq\sum_{t=m+1}^{T}(\mathbb{I}\\{F_{t}\\}+\mathbb{I}\\{\lnot
F_{t},S_{t}\in S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\})$
$\displaystyle\leq(T-m)(1-\beta)+\mathbb{I}\\{\lnot F_{t},S_{t}\in
S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\}\,.$

By leveraging the monotonicity and smoothness assumptions of the reward
function, we show that $\mathbb{P}(\\{\lnot F_{t},E_{t},S_{t}\in
S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\})=0$. Therefore, by the
inclusion-exclusion principle,

$\displaystyle\mathbb{P}(\\{\lnot F_{t},S_{t}\in
S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\})$
$\displaystyle\leq\mathbb{P}(\lnot E_{t})\leq 2m\cdot t^{-2}\,.$

Leveraging the upper bound of total number of pulls of suboptimal arm subsets,
the regret is bounded by

$\displaystyle\quad Regret_{\bm{\mu},\alpha,\beta}(T)$ $\displaystyle\leq
T\alpha\beta\cdot\text{OPT}_{\bm{\mu}}-\left(T\alpha\cdot\text{OPT}_{\bm{\mu}}-\mathbb{E}\left[\sum_{i=1}^{m}N_{i,T}\right]\cdot\Delta_{max}\right)$
$\displaystyle\leq
m\cdot\Delta_{max}\left(\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{T}}{\left(f^{-1}(\Delta_{min})\right)^{2}}+\frac{\pi^{2}}{3}+1\right)\,.\qed$

It remains in question whether a bandit algorithm can achieve a regret upper
bound sublinear in $B_{max}$. Our conjecture is negative. In fact, under
strategic manipulations of rewards, the design of robust bandit algorithms,
e.g. UCB and $\epsilon$-greedy, is analogous to the design of outlier-robust
mean estimation algorithms. Existing works on robust mean estimation, such as
Steinhardt et al. (2018), argue that from an information theoretical point of
view mean estimation error must be depending on the variance of the data.
Casting this argument to bandit with the strategic manipulation setting, we
believe that a tight regret bound is unlikely to be independent of the
strategic budget $B_{max}$. Moreover, Proposition 4 in Steinhardt et al.
(2018) implies that the dependency on $B_{max}$ is linear. This corresponds to
our linear dependency of regret in Theorem 2.

##  5\. Lower Bounds for strategic budget

To fully understand the effects of strategic manipulations, we investigate the
relationship between the strategic budget and the performance of UCB-based
algorithms. Our results provide the dependency between an arm’s strategic
budget and the number of times it is pulled, which influence the regret of the
algorithm incurred by the arm. Our analysis gains some insight from Zuo
(2020), which limits the discussion to the 2-armed bandit setting and cannot
be applied to the general MAB setting directly.

We first define some notations used in the theorem. Without loss of
generality, let arm $i^{\ast}$ be the optimal arm and arm $i,i\neq i^{\ast}$
be an arbitrary strategic suboptimal arm. Assume that arm $i$ has no access to
the information regarding other arms. Let $K_{i,t}$ and $K_{i^{\ast},t}$
denote the number of times arm $i$ and arm $i^{\ast}$ have been pulled up to
time $t$, respectively. Denote $\hat{\mu}_{i,t}$ as the empirical estimate of
the underlying mean $\mu$ without manipulations, i.e.,
$\hat{\mu}_{i,t}=\frac{\sum^{t-1}_{j=1}x_{i,j}}{K_{i,t-1}}$. Define the
suboptimality gap for each strategic arm $i$ to be
$\delta_{i}=\mu_{i^{\ast}}-\mu_{i}$. We use a slightly revised UCB algorithm
as the basic algorithm, where the UCB estimation term for arm $i$ is
$\hat{\mu}_{i,t}+\sqrt{\frac{2\log(K_{i,t}^{2}/\eta^{2})}{K_{i,t}}}$ and
$\eta$ is a confidence parameter chosen by the algorithm.

###### Theorem 1.

In stochastic multi-armed bandit problems, for a strategic suboptimal arm $i$
without access to other arms’ information, to be pulled for $\omega(k)$ in $T$
steps under the UCB algorithm where $k\geq O(\log{T})$, the minimum strategic
budget is $\omega(k)$.

This dependency of $k$ can be extended to CMAB and CUCB straightforwardly when
arms within an arm subset collude. Counter-intuitively, the dependency between
the number of pulls of a strategic arm and its strategic budget is linear and
subsequently, this infers that for a strategic arm to manipulate the algorithm
to suffer an undesired regret of $\omega(k)$, where $k\geq O(\log T)$, the
strategic budget must be at least $\omega(k)$.

##  6\. Experiments

In this section, we evaluate our SCUCB algorithm empirically on synthetic data
and three real applications, namely online worker selection in crowdsourcing,
online recommendation, and online influence maximization. We highlight the
best performance among all algorithms with bold text.

###  6.1. Baseline Algorithms

We compare our proposed SCUCB algorithm with both stochastic and adversarial
bandits algorithms that achieves optimal asymptotic regret in their settings.

  1. (1)

CUCB (Chen et al., 2013). CUCB is the naive counterpart of our algorithm. The
algorithm calculates an upper confidence interval for each arm and picks the
best arm subset with the highest upper confidence interval.

  2. (2)

TSCB (Wang and Chen, 2018). TSCB is the combinatorial version of the classical
Thompson sampling algorithm. The algorithm maintains a prior beta distribution
estimation for each arm and updates according to the received reward. At each
time, the algorithm samples from the estimated distributions and pick actions
according to the highest sample.

  3. (3)

Combinatorial variant of EXP3 (Auer et al., 2002b). The algorithm maintains a
weight for each arm and draws actions according to the normalized weight
distribution. Upon receiving rewards, the algorithm update weight according to
the classical EXP3 update rule.

###  6.2. Synthetic Experiments

We conduct experiments presented in this section with synthetic data and
compare our proposed algorithm with its naive counterpart. The approximation
oracle is designed to succeed with probability $1$. Each bandit arm is modeled
to follow a Bernoulli distribution with randomly populated $\mu\in[0,1]$ and
all arms adapt LSI strategy. The arms in the optimal arm subset have a
strategic budget of $0$ since an additional strategic budget for optimal arms
would only boost the performance of our algorithm. All other arms are equipped
with a randomly allocated budget $B$, $0\leq B\leq B_{max}$ by definition. As
is typical in the bandit literature, for example in Auer et al. (2002a), we
evaluate both the naive and strategic CUCB algorithms on their tuned versions,
where the UCB exploration parameter is scaled by a constant factor
$\gamma\in[0,1]$. To ensure reproducible results, each experiment is repeated
for $10$ random seeds and the averaged result is presented.

The first set of experiment is conducted with $K=\\{10,20\\}$ arms through a
time horizon of $T=5000$ time steps with maximum possible budget of
$B_{max}=\\{70,90,110,130\\}$. The algorithms are asked to select
$\text{Action size}=2$ arms as an arm subset at each time step. The cumulative
regret incurred by CUCB and SCUCB algorithm is presented in the table 1 where
the best performance is highlighted in bold text. Clearly, SCUCB demonstrated
its effectiveness as it achieves significantly smaller regrets in various
possible maximum strategic budgets.

Cumulative regret, Action size = 2, K = 10
---
Dataset | Synethetic
Bmax |  70 |  90 |  110 |  130
CUCB |  171.74 |  187.51 |  259.04 |  256.66
SCUCB |  143.85 |  172.57 |  208.53 |  233.57

Cumulative regret, Action size = 2, K = 20
---
Dataset | Synethetic
Bmax |  70 |  90 |  110 |  130
CUCB |  434.82 |  492.02 |  520.97 |  549.57
SCUCB |  301.57 |  365.94 |  450.10 |  505.453

Table 1. Cumulative regret achieved by CUCB and SCUCB with synthetic data with
various action size.

The next two tables reveals the advantage of SCUCB algorithm with various size
of action set. The experiments are conducted with time horizon of $T=5000$
time steps with $K=\\{10,20\\}$ arms and maximum possible budget of
$B_{max}=\\{50\\}$. The algorithms are asked to select $\text{Action
size}=\\{2,4,6,8\\}$ arms as an arm subset at each time step. Once again, our
SCUCB outperforms its naive counterpart by achieving much smaller cumulative
regret, the best numerical results across algorithms are highlighted in bold
text.

Cumulative regret, Bmax = 50, K = 10
---
Dataset | Synethetic
Action Size |  2 |  4 |  6 |  8
CUCB |  140.21 |  150.88 |  158.22 |  123.91
SCUCB |  105.58 |  113.63 |  103.42 |  88.72

Cumulative regret, Bmax = 50, K = 20
---
Dataset | Synethetic
Action Size |  2 |  4 |  6 |  8
CUCB |  302.10 |  316.09 |  340.52 |  328.80
SCUCB |  232.23 |  247.32 |  268.27 |  306.77

Table 2. Cumulative regret achieved by UCB and SCUCB with synthetic data with
various $B_{max}$.

To compare the two algorithms in detail, we plot the cumulative regret
incurred by algorithms against the time steps. It becomes apparent that the
SCUCB algorithm features a cumulative regret versus time steps line that is
much smaller than the one caused by CUCB even under a higher maximum possible
strategic budget. We compare the two algorithm under settings where the
maximize possible budget is $B_{max}=70,90$ and $B_{max}=110,130$.

Figure 2. 2 Comparison of CUCB and SCUCB with $B_{max}=70,90$. 2 Comparison of
CUCB and SCUCB with $B_{max}=110,130$.

###  6.3. Online Worker Selection in Crowdsourcing Systems

We simulated an online crowdsourcing system that has a workflow resembled by
figure 1 and model it as a combinatorial bandits problem. We performed an
extensive empirical analysis of our SCUCB algorithm against CUCB, the
combinatorial version of Thompson sampling, and EXP3. The experiments were
conducted with the Amazon sentiment dataset, where Amazon item reviews are
labeled ’is/is not book’ or ’is/is not negative (Krivosheev et al., 2018). We
split the dataset into two, where ’is book’ contains data that only has labels
’is/is not book’ and ’is negative’ contains data that only has labels ’is/is
not negative’. Both datasets consists of 7803 reviews, 284 workers, and 1011
tasks. The correctness of workers and tasks can be visualized by the figures
as below. Notice that most of the workers attain an accuracy of $60$ percent
and above. This highlights that most of the workers we are interacting with
has the ability to label most of the tasks correctly.

Figure 3. 3 Visualization of correctness of worker’s labels. 3Visualization of
correctness of task’s labels.

For each task, the data contains responses from 5 workers and the
crowdsourcing platform is asked to select 2, 3, or 4 workers at each time
step. To measure the performance of the algorithms, we made the assumption
that the reward is monotonically correlated to the accuracy of the label
compared to the ground truth label. Thus, we define the reward to be 1, if the
worker’s label is the same as ground truth label and 0 otherwise. To model the
strategic behavior of the workers, we model each worker with a randomly
allocated strategic level $s\in[0,1]$ such that the worker provides its honest
response with probability $s$.

For the first set of experiments, we choose the maximum possible strategic
budget to be $B_{max}=500$. For actions size of $2,3,4$. We obtain the
following cumulative rewards and cumulative regret results where the best
performance is highlighted in bold text. To ensure reproducible results, each
experiment is repeated 5 times and the averaged result is presented.

To further investigate the effect of the maximum possible strategic budget on
the performance of algorithms, we fix the size of action size to be 2 and plot
the cumulative reward/cumulative regret incurred by each algorithm again
$B_{max}\in[100,700]$. Regardless of the $B_{max}$ value, our proposed SCUCB
algorithm consistently outperforms other methods. For better visualization, we
omit the line for combinatorial Thompson sampling due to its relatively weaker
performance.

Figure 4. 4 Cumulative rewards attained by algorithms with various level of
$B_{max}$. 4 Cumulative regrets attained by algorithms with various level of
$B_{max}$.

The results of our crowdsourcing experiments reveal the robustness of our
SCUCB algorithm under strategic manipulations. It also indicates the
performance of adversarial and stochastic bandits algorithms under strategic
manipulations. The combinatorial variant of Thompson sampling is vulnerable
under manipulations, which agrees with our expectation given that the
algorithm is a Bayesian algorithm in nature and is heavily relying on
estimating the underlying distribution of arms. Its estimation can be easily
perturbed under strategic manipulation, and thus leads to undesired
performance results. It is also expected that the SCUCB algorithm far
outperforms its naive counterpart, CUCB algorithm. The combinatorial version
of EXP3 algorithm is the most competitive algorithm with our SCUCB. As the
EXP3 algorithm was originally designed for a pure adversarial setting, the
algorithm has some robustness under strategic manipulations. Shown in the
Figure 4 and Figure 4, the combinatorial EXP3 algorithm consistently shows
robustness across various levels of maximum possible strategic budget.
However, as our SCUCB algorithm considers the maximum possible strategic
budget and thus more adaptive, SCUCB far outperforms EXP3CB as $B_{max}$
increases.

Crowdsourcing (Cumulative Reward), Bmax = 500
---
Dataset | is_book
Action size |  2 |  3 |  4
CUCB |  31672.6 |  46181.2 |  68244.6
TSCB |  19853.0 |  34226.2 |  60621.2
EXP3 |  31569.6 |  46570.6 |  68482.2
SCUCB |  32082.6 |  46623.6 |  68524.6

Crowdsourcing (Cumulative Regret), Bmax = 500
---
Dataset | is_book
Action size |  2 |  3 |  4
CUCB |  27787.4 |  42198.8 |  48125.4
TSCB |  39607.0 |  54153.8 |  55748.8
EXP3 |  27890.4 |  41809.4 |  47887.8
SCUCB |  27377.4 |  41756.4 |  47845.4

Crowdsourcing (Cumulative Reward), Bmax = 500
---
Dataset | is_negative
Action size |  2 |  3 |  4
CUCB |  31108.8 |  44757.6 |  59424.8
TSCB |  17240.6 |  32010.4 |  51109.0
EXP3 |  30879.0 |  44767.2 |  58207.8
SCUCB |  31759.0 |  44843.4 |  59441.4

Crowdsourcing (Cumulative Regret), Bmax = 500
---
Dataset | is_negative
Action size |  2 |  3 |  4
CUCB |  28411.2 |  43566.2 |  56465.2
TSCB |  42279.4 |  56279.6 |  64781.0
EXP3 |  28641.0 |  43523.4 |  57682.2
SCUCB |  27761.0 |  43446.6 |  56448.6

Table 3. Cumulative rewards and cumulative regret attained by SCUCB and
baseline algorithms with various action sizes on isbook dataset and isnegative
dataset.

###  6.4. Online Recommendation System

The online recommendation is a classic example of combinatorial bandits in
applications. We evaluated algorithms in the latest MovieLens dataset which
contains 9742 movies and 100837 ratings of the movies with each rating being
$1-5$ (Harper and Konstan, 2015). We compare the algorithms based on the total
values of ratings received, i.e. recommending a movie and receiving a rating
of 5 is more desired than recommending a movie and receiving a rating of 1.

As the dataset may consist of unbalanced data for each movie, we adapted
collaborative filtering and $k$-means clustering into our evaluation system.
We used the collaborative filtered for training and testing and instead of
recommending movies, we clustered the movies by $k$-means clustering and asked
the bandits algorithm to choose one cluster at each time. The movie with the
highest rating in the chosen cluster is recommended. The workflow of the
experiment setup is summarized in the above diagram.

We performed the evaluation with various number of clusters (10, 20 or 30) and
$B_{max}=30,50,70$ through a time horizon of $T=500$. The results presented
below are averages over 5 runs to ensure reproducibility. The best performance
across algorithms is highlighted in bold text. From the tables below, we
conclude the effectiveness of SCUCB algorithm.

Recsys (Cumulative Reward), T=500, 10 clusters
---
Dataset | Movielens
Bmax |  30 |  50 |  70
UCB |  2297.60 |  2494.36 |  2631.02
TS |  2160.14 |  2314.76 |  2468.26
EXP3 |  2181.11 |  2449.28 |  2430.96
SUCB |  2305.75 |  2314.76 |  2636.07

Recsys (Cumulative Reward), T=500, 20 clusters
---
Dataset | Movielens
Bmax |  30 |  50 |  70
UCB |  2469.93 |  2336.92 |  2159.25
TS |  2260.20 |  1850.55 |  1905.42
EXP3 |  2380.74 |  2317.82 |  2025.39
SUCB |  2474.69 |  2341.19 |  2177.70

Recsys (Cumulative Reward), T=500, 30 clusters
---
Dataset | Movielens
Bmax |  30 |  50 |  70
UCB |  2443.57 |  2393.88 |  2472.31
TS |  2132.16 |  2248.56 |  1855.14
EXP3 |  2368.42 |  2265.32 |  2339.49
SUCB |  2436.43 |  2397.72 |  2476.52

Table 4. Cumulative rewards attained by algorithms with different number of
clusters $10,20,30$ and different level of $\\{B_{max}=30,50,70\\}$ across 500
time steps.  Figure 5. Experiment set up of online recommendation.

###  6.5. Online Influence Maximization

We implemented the online influence maximization with an offline influence
maximization algorithm TIM as our oracle (Tang et al., 2014). TIM is one of
the offline influence maximization algorithms that achieve asymptotic
optimality. We perform the experiments on two datasets. One is a simulation
dataset with 16 nodes and 44 edges, the other is a 100 nodes subset from Digg
dataset, where each node represents a user from Digg website (Rossi and Ahmed,
2015). We simulate the connectivity of edges at each time step by randomly
assigning each edge a connectivity probability at the start of the experiment.

Figure 6. Visualization of synthetic graph for evaluation. Figure 7.  Mean
rewards attained by algorithms.

Figure 6 visualizes the synthetic graph we created for evaluation. We then
tested the algorithms over $T=800$ time steps with action size of 2 and
maximum possible strategic budget of $B_{max}=300$. Figure 7 shows the
effectiveness of algorithms by evaluating based on the averaged nodes
influenced. To ensure reproducible results, we calculate the mean of influence
spread over 100 trials. For better visualization, we kept a running mean of
over 50 time steps to smooth the lines.

We then investigate the effect of action size and the results are summarized
in the following tables 5.

OIM (Averaged Final Reward), Bmax = 200
---
Dataset | Synthetic, 16 nodes, 44 edges |
Action size |  2 |  4 |  6 |  8
CUCB |  5.46 |  6.54 |  10.4 |  12.5
TSCB |  6.7 |  8.50 |  10.44 |  12.7
EXP3CB |  5.86 |  8.14 |  10.34 |  12.46
SCUCB |  7.44 |  9.32 |  11.16 |  13.04
OIM (Averaged Final Reward), Bmax = 200
---
Dataset | digg, 100 nodes
Action size |  10 |  15 |  20
CUCB |  15.64 |  20.64 |  25.32
TSCB |  16.30 |  21.62 |  26.08
EXP3 |  12.16 |  17.76 |  21.72
SCUCB |  16.56 |  22.16 |  26.14
Table 5. Averaged final rewards attained by algorithms with synthetic and Digg
dataset with action size of 2, 800 time steps and $B_{max}=200$.

##  7\. Conclusion

We investigate the problem of combinatorial MAB under strategic manipulations
of rewards. We propose a variant of the UCB algorithm, SCUCB, which attains a
regret at most $O(m\log T+mB_{max})$. Compared to previous studies on the
bandit problems under strategic manipulations, we relax on the assumption that
the algorithm has access to the cumulative strategic budget spent by each arm
at each time step. For the robustness of bandit algorithms, we present lower
bounds on the strategic budget for a malicious arm to incur a $\omega(\log T)$
regret of the bandit algorithm.

We provide extensive empirical results on both synthetic and real datasets
with a range of applications to verify the effectiveness of the proposed
algorithm. Our algorithm consistently outperforms baseline algorithms that
were designed for stochastic and adversarial settings.

## References

  * (1)
  * Altschuler et al. (2019) Jason Altschuler, Victor-Emmanuel Brunel, and Alan Malek. 2019.  Best arm identification for contaminated bandits.  _Journal of Machine Learning Research_ 20, 91 (2019), 1–39.
  * Anantharam et al. (1987) Venkatachalam. Anantharam, Pravin. Varaiya, and Jean. Walrand. 1987\.  Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: I.I.D. rewards.  _IEEE Trans. Automat. Control_ 32, 11 (Nov. 1987), 968–976.
  * Auer et al. (2002a) Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. 2002a.  Finite-time analysis of the multiarmed bandit problem.  _Machine Learning_ 47, 2 (2002), 235–256.
  * Auer et al. (2002b) Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. 2002b.  The nonstochastic multiarmed bandit problem.  _SIAM J. Comput._ 32, 1 (Jan. 2002), 48–77.
  * Auer et al. (2002c) Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E Schapire. 2002c.  The nonstochastic multiarmed bandit problem.  _SIAM J. Comput._ 32, 1 (2002), 48–77.
  * Berry and Fristedt (1985) Donald A Berry and Bert Fristedt. 1985.  _Bandit problems: Sequential allocation of experiments (Monographs on statistics and applied probability)_.  Springer.
  * Bogunovic et al. (2020) Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. 2020.  Stochastic linear bandits robust to adversarial attacks.  _arXiv:2007.03285 [cs, stat]_ (Oct. 2020).
  * Bouneffouf et al. (2021) Djallel Bouneffouf, Amel Bouzeghoub, and Alda Lopes Gançarski. 2021\.  A contextual-bandit algorithm for mobile context-aware recommender system. In _Neural Information Processing - 19th International Conference, ICONIP_ , Tingwen Huang, Zhigang Zeng, Chuandong Li, and Chi-Sing Leung (Eds.). Doha, Qatar.
  * Braverman et al. (2019) Mark Braverman, Jieming Mao, Jon Schneider, and S. Matthew Weinberg. 2019.  Multi-armed bandit problems with strategic arms. In _Proceedings of the Thirty-Second Conference on Learning Theory_. Phoenix, USA.
  * Cesa-Bianchi and Lugosi (2006) Nicolò Cesa-Bianchi and Gábor Lugosi. 2006.  _Prediction, learning, and games_.  Cambridge University Press.
  * Chen et al. (2013) Wei Chen, Yajun Wang, and Yang Yuan. 2013.  Combinatorial multi-Armed bandit: general framework and applications. In _Proceedings of the 30th International Conference on Machine Learning_. Atlanta, Georgia, USA.
  * Combes et al. (2015) Richard Combes, Mohammad Sadegh Talebi, Alexandre Proutière, and Marc Lelarge. 2015\.  Combinatorial bandits revisited. In _Advances in Neural Information Processing Systems_. Montreal, Quebec, Canada., 2116–2124.
  * Durand et al. (2018) Audrey Durand, Charis Achilleos, Demetris Iacovides, Katerina Strati, Georgios D. Mitsis, and Joelle Pineau. 2018.  Contextual bandits for adapting treatment in a mouse model of de Novo Carcinogenesis. In _Proceedings of the 3rd Machine Learning for Healthcare Conference_ _(Proceedings of Machine Learning Research)_. Palo Alto, California.
  * Feng et al. (2020) Zhe Feng, David Parkes, and Haifeng Xu. 2020.  The intrinsic robustness of stochastic bandits to strategic manipulation. In _Proceedings of the 37th International Conference on Machine Learning_.
  * Gajane et al. (2018) Pratik Gajane, Tanguy Urvoy, and Emilie Kaufmann. 2018\.  Corrupt bandits for preserving local privacy. In _Proceedings of Algorithmic Learning Theory_. Lanzarote, Spain.
  * Garcelon et al. (2020) Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. 2020\.  Adversarial attacks on linear contextual bandits.  _arXiv:2002.03839 [cs, stat]_ (Oct. 2020).
  * Gupta et al. (2019) Anupam Gupta, Tomer Koren, and Kunal Talwar. 2019\.  Better algorithms for stochastic bandits with adversarial corruptions. In _Proceedings of the Thirty-Second Conference on Learning Theory_. Phoenix, USA.
  * Harper and Konstan (2015) F. Maxwell Harper and Joseph A. Konstan. 2015.  The MovieLens Datasets: History and Context.  _ACM Trans. Interact. Intell. Syst._ 5, 4, Article 19 (Dec. 2015), 19 pages.  https://doi.org/10.1145/2827872
  * Jain et al. (2014) Shweta Jain, Sujit Gujar, Onno Zoeter, and Y Narahari. 2014\.  A quality assuring multi-armed bandit crowdsourcing mechanism with incentive compatible learning. In _Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems_. 1609–1610.
  * Jun et al. (2018) Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. 2018\.  Adversarial attacks on stochastic bandits. In _Advances in Neural Information Processing Systems_. Montreal, Canada, 3640–3649.
  * Krivosheev et al. (2018) Evgeny Krivosheev, Fabio Casati, Marcos Baez, and Boualem Benatallah. 2018.  Combining Crowd and Machines for Multi-predicate Item Screening.  _Proc. ACM Hum.-Comput. Interact._ 2, CSCW, Article 97 (Nov. 2018), 18 pages.  https://doi.org/10.1145/3274366
  * Kveton et al. (2015) Branislav Kveton, Wen Zheng, Azin Ashkan, and Csaba Szepesvári. 2015.  Tight regret bounds for stochastic combinatorial semi-bandits. In _Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics_. San Diego, California, USA.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári. 2020.  Bandit algorithms.  _Cambridge University Press_ (Jun 2020).
  * Li et al. (2019) Shuai Li, Wei Chen, Shuai Li, and Kwong-Sak Leung. 2019\.  Improved Algorithm on Online Clustering of Bandits. In _Proceedings of the 28th International Joint Conference on Artificial Intelligence_ (Macao, China) _(IJCAI’19)_. AAAI Press, 2923–2929.
  * Li et al. (2020a) Shuai Li, Wei Chen, Zheng Wen, and Kwong-Sak Leung. 2020a.  Stochastic online learning with probabilistic graph feedback. In _Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI)_. New York, USA.
  * Li et al. (2020b) Shuai Li, Fang Kong, Kejie Tang, Qizhi Li, and Wei Chen. 2020b.  Online influence maximization under linear threshold model.  arXiv:2011.06378 [cs.LG]
  * Li et al. (2016) Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. 2016\.  Contextual combinatorial cascading bandits. In _Proceedings of The 33rd International Conference on Machine Learning_. New York, New York, USA.
  * Liu and Shroff (2019) Fang Liu and Ness Shroff. 2019.  Data poisoning attacks on stochastic bandits. In _Proceedings of the 36th International Conference on Machine Learning_. Long Beach, California, USA.
  * Lykouris et al. (2018) Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. 2018\.  Stochastic bandits robust to adversarial corruptions. In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_. Los Angeles, CA, USA.
  * Rangi and Franceschetti (2018) Anshuka Rangi and Massimo Franceschetti. 2018.  Multi-armed bandit algorithms for crowdsourcing systems with online estimation of workers’ ability. In _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_. 1345–1352.
  * Rejwan and Mansour (2020) Idan Rejwan and Yishay Mansour. 2020.  Top-$k$ combinatorial bandits with full-bandit feedback. In _Proceedings of the 31st International Conference on Algorithmic Learning Theory_. San Diego, California, USA.
  * Robbins (1952) Herbert Robbins. 1952\.  Some aspects of the sequential design of experiments.  _Bull. Amer. Math. Soc._ 58, 5 (1952), 527–535.
  * Rossi and Ahmed (2015) Ryan A. Rossi and Nesreen K. Ahmed. 2015.  The Network Data Repository with Interactive Graph Analytics and Visualization. In _AAAI_.  http://networkrepository.com
  * Sankararaman and Slivkins (2018) Karthik Abinav Sankararaman and Aleksandrs Slivkins. 2018.  Combinatorial semi-bandits with knapsacks. In _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_. Playa Blanca, Lanzarote, Canary Islands.
  * Steinhardt et al. (2018) Jacob Steinhardt, Moses Charikar, and Gregory Valiant. 2018\.  Resilience: A criterion for learning in the presence of arbitrary outliers. In _9th Innovations in Theoretical Computer Science Conference_. Dagstuhl, Germany.
  * Talebi et al. (2018) M. Sadegh. Talebi, Zhenhua Zou, Richard Combes, Alexandre Proutiere, and Mikael Johansson. 2018\.  Stochastic online shortest path routing: The value of feedback.  _IEEE Trans. Automat. Control_ 63, 4 (2018), 915–930.
  * Tang et al. (2014) Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014.  Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency. In _Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data_ (Snowbird, Utah, USA) _(SIGMOD ’14)_. Association for Computing Machinery, New York, NY, USA, 75–86.
  * Thompson (1933) William R. Thompson. 1933\.  On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples.  _Biometrika_ 25, 3/4 (1933), 285–294.
  * Tran-Thanh et al. (2014) Long Tran-Thanh, Sebastian Stein, Alex Rogers, and Nicholas R Jennings. 2014.  Efficient crowdsourcing of unknown experts using bounded multi-armed bandits.  _Artificial Intelligence_ 214 (2014), 89–111.
  * Vaswani et al. (2017) Sharan Vaswani, Branislav Kveton, Zheng Wen, Mohammad Ghavamzadeh, Laks V. S. Lakshmanan, and Mark Schmidt. 2017.  Model-independent online learning for influence maximization. In _Proceedings of the 34th International Conference on Machine Learning_. International Convention Centre, Sydney, Australia.
  * Wang and Chen (2018) Siwei Wang and Wei Chen. 2018.  Thompson sampling for combinatorial semi-bandits. In _International Conference on Machine Learning_. PMLR, 5114–5122.
  * Wang et al. (2017) Yingfei Wang, Hua Ouyang, Chu Wang, Jianhui Chen, Tsvetan Asamov, and Yi Chang. 2017\.  Efficient ordered combinatorial semi-bandits for whole-page recommendation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ (Feb 2017).
  * Wei and Luo (2018) Chen-Yu Wei and Haipeng Luo. 2018.  More adaptive algorithms for adversarial bandits. In _Proceedings of the 31st Conference on Learning Theory_. Stockholm, Sweden.
  * Yang et al. (2020) Lin Yang, Mohammad Hajiesmaili, Mohammad Sadegh Talebi, John C. S. Lui, and Wing Shing Wong. 2020\.  Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm. In _Advances in Neural Information Processing Systems_. virtual.
  * Zimmert et al. (2019) Julian Zimmert, Haipeng Luo, and Chen-Yu Wei. 2019.  Beating stochastic and adversarial semi-bandits optimally and simultaneously. In _Proceedings of the 36th International Conference on Machine Learning_. Long Beach, California, USA.
  * Zuo (2020) Shiliang Zuo. 2020\.  Near optimal adversarial attack on UCB bandits.  _arXiv:2008.09312 [cs, stat]_ (Aug. 2020).

##  Appendix A Regret analysis of strategic UCB

###### Lemma 1 (Re-statement).

Let
$\Lambda_{i,t}=\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{\rho_{i,t-1}}{K_{i,t-1}}$,
where $\rho_{i,t-1}$ is the total strategic budget spent by arm $i$ up to time
$t-1$ and $K_{i,t-1}$ be the total number of pulls of arm $i$ up to time
$t-1$. Define the event $E_{t}=\\{|\
\widetilde{\mu}_{i,t-1}-\mu_{i}|\leq\Lambda_{i,t},\forall i\in[m]\\}$, where
$\mu_{i}$ is the true mean of arm $i$’s underlying distribution. Then,
$\mathbb{P}(\lnot E_{t})\leq 2m\cdot t^{-2}$.

###### Proof.

Denote $\hat{\mu}_{i,t-1}=\frac{\sum_{j=1}^{t-1}x_{i,j}}{K_{i,t-1}}$ as the
estimation of the expected reward without the manipulated variable $z_{i,t}$.
By the definition of $\hat{\mu}_{i,t}$ and $\widetilde{\mu}_{i,t}$,

$\displaystyle\mathbb{P}\left(|\widetilde{\mu}_{i,t-1}-\mu_{i}|>\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{\rho_{i,t-1}}{K_{i,t-1}}\right)$
$\displaystyle=\ $
$\displaystyle\mathbb{P}\left(\left|\hat{\mu}_{i,t-1}+\frac{\rho_{i,t-1}}{K_{i,t-1}}-\mu_{i}\right|>\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{\rho_{i,t-1}}{K_{i,t-1}}\
\right)$ $\displaystyle=\ $
$\displaystyle\mathbb{P}\left(\hat{\mu}_{i,t-1}-\mu_{i}>\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}\
\right)+\mathbb{P}\left(\hat{\mu}_{i,t-1}-\mu_{i}<-\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}-2\frac{\rho_{i,t-1}}{K_{i,t-1}}\right)$
$\displaystyle\leq\ $
$\displaystyle\mathbb{P}\left(\hat{\mu}_{i,t-1}-\mu_{i}>\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}\
\right)+\mathbb{P}\left(\hat{\mu}_{i,t-1}-\mu_{i}<-\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}\right)$
$\displaystyle=\ $
$\displaystyle\sum_{s=1}^{t-1}\mathbb{P}\left(|\hat{\mu}_{i,t-1}-\mu_{i}|>\sqrt{\frac{3\log{t}}{2s}},K_{i,t-1}=s\
\right)$ $\displaystyle\leq\ $
$\displaystyle\sum_{s=1}^{t-1}\mathbb{P}\left(|\hat{\mu}_{i,{t-1}}-\mu_{i}|>\sqrt{\frac{3\log{t}}{2s}}\
\right)$ $\displaystyle\leq\ $ $\displaystyle
2t\cdot\exp{(-3\log{t})}=\frac{2}{t^{2}}\,,$

where the last inequality follows the Chernoff-Hoeffding bound. By the union
bound,

$\quad\mathbb{P}(\lnot
E_{t})=\mathbb{P}\left(\\{|\widetilde{\mu}_{i,t-1}-\mu_{i}|>\Lambda_{i,t},\forall
i\in[m]\\}\right)\leq 2m\cdot t^{-2}\,.\qed$

###### Theorem 2 (Re-statement).

The regret of the strategic CUCB algorithm with m strategic arms in time
horizon $T$ using an $(\alpha,\beta)$-approximation oracle is at most

$\displaystyle
m\cdot\Delta_{max}\left(\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{T}}{\left(f^{-1}(\Delta_{min})\right)^{2}}+\frac{\pi^{2}}{3}+1\right)\,,$

where $f^{-1}(\cdot)$ is the inverse bounded smoothness function.

###### Proof.

We start by introducing a few notations. Let $F_{t}$ to be the event where the
$(\alpha,\beta)$-approximation oracle fails to produce an
$\alpha$-approximation answer with respect to the input
$\bm{\bar{\mu}}=(\bar{\mu}_{1,t},\bar{\mu}_{2,t},.....,\bar{\mu}_{m,t})$ at
time $t$. By definition of a $(\alpha,\beta)$-approximation oracle, we have
$\mathbb{P}(F_{t})\leq 1-\beta$. Observe that at an arbitrary time $t$, a
suboptimal arm subset may be selected due to two reasons, i) the
$(\alpha,\beta)$-approximation oracle fails to provide an $\alpha$-approximate
arm subset with respect to the input vector
$\bm{\bar{\mu}}=(\bar{\mu}_{1,t},\bar{\mu}_{2,t},.....,\bar{\mu}_{m,t})$ and
ii) the estimated mean vector
$\bm{\bar{\mu}}=(\bar{\mu}_{1,t},\bar{\mu}_{2,t},......,\bar{\mu}_{m,t})$
deviates from true values by a significant amount.

To account for $\sum^{T}_{t=1}\mathbb{I}(S_{t}\in S_{B})$,where
$\mathbb{I}(S_{t}\in S_{B})$ is 1 when algorithm choose a suboptimal arm
subset, $S_{t}\in S_{B}$, at time $t$, we introduce a counter $N_{i}$ for each
arm $i\in[m]$ after the $m$-round initialization and let $N_{i,t}$ be the
value of $N_{i}$ at time $t$. We initialize $N_{i,m}=1$. By definition,
$\sum_{i\in[m]}N_{i,m}=m$. For $t>m$, the counter $N_{i,t}$ is updated as
follows.

  * •

If $S_{t}\in S_{B}$, then $N_{{i^{\prime}},t}=N_{{i^{\prime}},t-1}+1$ where
$i^{\prime}=\operatorname*{arg\,min}_{i\in S_{t}}N_{i,t-1}$. In the case that
$i^{\prime}$ is not unique, we break ties arbitrarily.

  * •

If $S_{t}\not\in S_{B}$, no counters will be updated then.

As such, the total number of pulls of suboptimal arm subsets is less than or
equal to $\sum_{i=1}^{m}N_{i,T}$.

Define
$\psi_{t}=\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{t}}{\left(f^{-1}(\Delta_{min})\right)^{2}}>c\,,$
where $c$ is the larger solution of the following equation,

(1)
$\displaystyle\frac{\left(f^{-1}(\Delta_{min})\right)^{2}}{4}c^{2}-\left(2B_{max}f^{-1}(\Delta_{min})+\frac{3\log{t}}{2}\right)c+4B_{max}^{2}=0\,.$

By solving Equation (1), we have

(2) $\displaystyle c$
$\displaystyle=\frac{2\left(2B_{max}f^{-1}(\Delta_{min})+\frac{3\log{t}}{2}\right)}{\left(f^{-1}(\Delta_{min})\right)^{2}}+\frac{2\sqrt{\left(2B_{max}f^{-1}(\Delta_{min})+\frac{3\log{t}}{2}\right)^{2}-4(f^{-1}(\Delta_{min}))B_{max}}}{\left(f^{-1}(\Delta_{min})\right)^{2}}\,.$

We then decompose the total number $\sum_{i=1}^{m}N_{i,T}$ of pulls of
suboptimal arm subsets as

$\displaystyle\quad\sum_{i=1}^{m}N_{i,T}$
$\displaystyle=m+\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in S_{B}\\}$
$\displaystyle=m+\sum_{t=m+1}^{T}\sum_{i\in[m]}^{m}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t}>N_{i,t-1},N_{i,t-1}\leq\psi_{t}\\}+\sum_{t=m+1}^{T}\sum_{i\in[m]}^{m}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t}>N_{i,t-1},N_{i,t-1}>\psi_{t}\\}$ $\displaystyle\leq
m+m\psi_{T}+\sum_{t=m+1}^{T}\sum_{i\in[m]}^{m}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t}>N_{i,t-1},N_{i,t-1}>\psi_{t}\\}$ (3)
$\displaystyle=m+m\psi_{T}+\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in S_{B},\forall
i\in S_{t},N_{i,t-1}>\psi_{t}\\}\,.$

The first inequality follows as $\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in
S_{B},\forall i\in S_{t},N_{i,t-1}\leq\psi_{t}\\}$ can be trivially upper
bounded by $\psi_{t}$ and the second equality holds by our rule of updating
the counters.

The third term of Equation (3) can be further decomposed according to whether
the oracle fails,

$\displaystyle\quad\sum_{t=m+1}^{T}\mathbb{I}\\{S_{t}\in
S_{B},N_{i,t-1}>\psi_{t},\forall i\in S_{t}\\}$ (4)
$\displaystyle\leq\sum_{t=m+1}^{T}(\mathbb{I}\\{F_{t}\\}+\mathbb{I}\\{\lnot
F_{t},S_{t}\in S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\})$
$\displaystyle=(T-m)(1-\beta)+\sum_{t=m+1}^{T}\mathbb{I}\\{\lnot
F_{t},S_{t}\in S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\}\,.$

Let
$\Lambda_{i,t}=\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{\rho_{i,t-1}}{K_{i,t-1}}$
where $\rho_{i,t-1}$ is the total strategic budget spent by arm $i$ up to time
$t-1$. Define event $E_{t}=\\{|\
\widetilde{\mu}_{i,t-1}-\mu_{i}|\leq\Lambda_{i,t},\forall i\in[m]\\}$, where
$\mu_{i}$ is the true mean of arm $i$’s underlying distribution without
manipulation. We continue the proof under $\mathbb{P}(\\{E_{t},\lnot
F_{t},S_{t}\in S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\})=0$ and prove it
afterwards.

Since $\mathbb{P}\left(\\{E_{t},\lnot F_{t},S_{t}\in
S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\}\right)=0$, by inclusion-
exclusion principle, $\mathbb{P}(\\{\lnot F_{t},S_{t}\in
S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\})\leq\mathbb{P}(\lnot E_{t})\,.$
Denote $\hat{\mu}_{i,t-1}=\frac{\sum_{j=1}^{t-1}x_{i,j}}{K_{i,t-1}}$ as the
estimation of the expected reward without the manipulated variable $z_{i,t}$.
By the definition of $\hat{\mu}_{i,t}$ and $\widetilde{\mu}_{i,t-1}$,

$\displaystyle\quad\mathbb{P}\left(|\widetilde{\mu}_{i,t-1}-\mu_{i}|>\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{\rho_{i,t-1}}{K_{i,t-1}}+\frac{B_{max}}{K_{i,t-1}}\
\right)$
$\displaystyle=\mathbb{P}\left(\left|\hat{\mu}_{i,t-1}+\frac{\rho_{i,t-1}}{K_{i,t-1}}-\mu_{i}\right|>\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{\rho_{i,t-1}}{K_{i,t-1}}+\frac{B_{max}}{K_{i,t-1}}\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\hat{\mu}_{i,t-1}+\frac{\rho_{i,t-1}}{K_{i,t-1}}-\mu_{i}\right|>\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{\rho_{i,t-1}}{K_{i,t-1}}\
\right)$ (5) $\displaystyle\leq 2t^{-2}\,,$

where the last inequality holds due to Lemma 1.

By the union bound,

$\displaystyle\ \quad\mathbb{P}(\lnot
E_{t})=\mathbb{P}(\\{|\widetilde{\mu}_{i,t-1}-\mu_{i}|>\Lambda_{i,t},\forall
i\in[m]\\}\ )\leq 2m\cdot t^{-2}\,.$

Hence,

$\displaystyle\mathbb{P}(\\{\lnot F_{t},S_{t}\in S_{B},\forall i\in
S_{t},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\})\leq\mathbb{P}(\lnot E_{t})\leq
2m\cdot t^{-2}\,.$

We now show that $\mathbb{P}(\\{E_{t},\lnot F_{t},S_{t}\in
S_{B},K_{i,t-1}>\psi_{t},\forall i\in S_{t}\\})=0$. Let
$\Lambda=\sqrt{\frac{3\log{t}}{2\psi_{t}}}+\frac{2B_{max}}{\psi_{t}}$, which
is not a random variable, and $B_{max}=max_{i\in[m]}B_{i}$, where $B_{i}$ is
the strategic budget for arm $i$. For variable $\Lambda_{i,t}$, let
$\Lambda_{i,t}^{\ast}=\max\\{\Lambda_{i,t}\\}$. Since $K_{i,t-1}>\psi_{t}$ and
$B_{max}\geq B_{i}\geq\rho_{i}$, we have $\Lambda>\Lambda_{i,t}^{\ast}$.
According to line 7 of Algorithm 1, we have
$\bar{\mu}_{i,t}=\widetilde{\mu}_{i,t-1}+\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{B_{max}}{K_{i,t-1}}$
and
$\bar{\mu}_{i,t}=\hat{\mu}_{i,t-1}+\frac{\rho_{i,t-1}}{K_{i,t-1}}+\sqrt{\frac{3\log{t}}{2K_{i,t-1}}}+\frac{B_{max}}{K_{i,t-1}}$.
Thus, $|\hat{\mu}_{i,t-1}-\mu_{i}|\leq\Lambda_{i,t}$ implies that
$0<\bar{\mu}_{i,t-1}-\mu_{i}\leq 2\Lambda_{i,t}\leq 2\Lambda_{i,t}^{\ast}\leq
2\Lambda$, for $i\in S_{t}$.

Recall $S^{\ast}=\operatorname*{arg\,max}_{S\in\mathbb{S}}r_{\bm{\mu}}(S)$ and
${OPT}_{\bm{\mu}}=\max_{S\in\mathbb{S}}r_{\bm{\mu}}(S)$. Suppose
$\\{E_{t},\lnot F_{t},S_{t}\in S_{B},\forall i\in S_{t},K_{i,t-1}>\psi_{t}\\}$
happens at time $t$, the following holds

$\displaystyle\quad r_{\bm{\mu}}(S_{t})+f(2\Lambda)\geq
r_{\bm{\mu}}(S_{t})+f(2\Lambda_{i,t}^{\ast})\geq
r_{\bm{\bar{\mu}}}(S_{t})\geq\alpha\cdot{OPT}_{\bar{\bm{\mu}}}\geq\alpha\cdot
r_{\bar{\bm{\mu}}}(S^{\ast}_{\bm{\mu}})\geq\alpha\cdot
r_{{\bm{\mu}}}(S^{\ast}_{\bm{\mu}})=\alpha\cdot{OPT}_{\bm{\mu}}\,.$

The first inequality is due to the strict monotonicity of $f(\cdot)$ and
$\Lambda>\Lambda_{i,t}^{\ast}$. The second inequality is due to the bounded
smoothness property and $|\bar{\mu}_{i,t-1}-\mu_{i}|\leq 2\Lambda_{i,t}$. The
third inequality is due to the fact that $\lnot F_{t}$ implies
$S_{t}\geq\alpha\cdot opt_{\bm{\mu}}$. The forth inequality is by the
definition of $opt_{\bm{\mu}}$. The last inequality is is due to the
monotonicity of $r_{\bm{\mu}}(S)$ and $0<\bar{\mu}_{i,t-1}-\mu_{i}$.

Let $\kappa=\sqrt{\frac{3\log{t}}{2c}}+\frac{2B_{max}}{c}$ where $c$ takes the
value defined in Equation (1). Given $\psi_{t}>c$, we have
$\Lambda=\sqrt{\frac{3\log{t}}{2\psi_{t}}}+\frac{2B_{max}}{\psi_{t}}<\kappa$.
By Equation (2), we have $f(2\Lambda)<f(2\kappa)=\Delta_{min}$ and
$\Delta_{min}>\alpha\cdot opt_{\bm{\mu}}-r_{\bm{\mu}}(S_{t})$, which
contradicts the definition of $\Delta_{min}$ and the fact that $S_{t}\in
S_{B}$. Therefore,

$\mathbb{P}(E_{t},\lnot F_{t},S_{t}\in S_{B},\forall i\in
S_{t},K_{i,t-1}>\psi_{t})=0\,.$

Based on the above analysis, we can upper bound the total number of suboptimal
pulls as

$\displaystyle\mathbb{E}\left[\sum_{i=1}^{m}N_{i,T}\right]$ $\displaystyle\leq
m(1+\psi_{T})+(T-m)(1-\beta)+\sum_{t=m+1}^{T}\frac{2m}{t^{2}}$ (6)
$\displaystyle=m\left(1+\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{T}}{\left(f^{-1}(\Delta_{min})\right)^{2}}\right)+(T-m)(1-\beta)+\sum_{t=m+1}^{T}\frac{2m}{t^{2}}\,.$

Since the cumulative regret relate closely to the total number of suboptimal
pulls $\mathbb{E}[\sum_{i=1}^{m}N_{i,T}]$, the upper bound of cumulative
regret is thus

$\displaystyle\quad Regret_{\bm{\mu},\alpha,\beta}(T)$ $\displaystyle\leq
T\cdot\alpha\beta\text{OPT}_{\bm{\mu}}-\left(T\cdot\alpha\text{OPT}_{\bm{\mu}}-\mathbb{E}\left[\sum_{i=1}^{m}N_{i,T}\right]\Delta_{max}\right)$
$\displaystyle=(\beta-1)T\cdot\alpha\text{OPT}_{\bm{\mu}}+\Delta_{max}\left(m\left(1+\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{T}}{\left(f^{-1}(\Delta_{min})\right)^{2}}\right)+(T-m)(1-\beta)+\sum_{t=m+1}^{T}\frac{2m}{t^{2}}\right)$
$\displaystyle\leq((T-m)\cdot\Delta_{max}-T\cdot\alpha\text{OPT}_{\bm{\mu}})(1-\beta)+m\cdot\Delta_{max}\left(1+\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{T}}{\left(f^{-1}(\Delta_{min})\right)^{2}}+\frac{\pi^{2}}{3}\right)\,.$

Each time the algorithm pull a suboptimal arm subset $S_{t}\in S_{B}$ at time
$t$, the algorithm incur an additional regret of at most $\Delta_{max}$, which
is less than or equal to $\alpha\cdot opt_{\bm{\mu}}$. Thus,

$\displaystyle\quad(T-m)\Delta_{max}-T\alpha\cdot\text{OPT}_{\bm{\mu}}$
$\displaystyle\leq(T-m)\alpha\cdot\text{OPT}_{\bm{\mu}}-T\alpha\cdot\text{OPT}_{\bm{\mu}}$
$\displaystyle=-m\alpha\cdot\text{OPT}_{\bm{\mu}}<0\,.$

As a result, the regret of the strategic CUCB algorithm under strategic
manipulations of reward is at most

$\displaystyle Regret_{\bm{\mu},\alpha,\beta}(T)\leq
m\cdot\Delta_{max}\left(\frac{8B_{max}f^{-1}(\Delta_{min})+6\log{T}}{\left(f^{-1}(\Delta_{min})\right)^{2}}+\frac{\pi^{2}}{3}+1\right)\,.$

∎

##  Appendix B Lower bound on the strategic budget

###### Theorem 1.

In stochastic multi-armed bandit problems, for a strategic suboptimal arm $i$,
under time horizon $T$ and without access to other arms’ information, the
minimum strategic budget needed for it to be pulled $\omega(\log{T})$ is
$\omega(\log{T})$. The regret incurred for any bandits learning algorithm is
thus $\omega(\log{T})$.

###### Proof.

Let time $t\in[1,T]$ be the time step arm $i$ is last pulled under UCB
algorithm and $\eta$ is a parameter chosen by the algorithm. The following
inequality must stands at time $t$,

$\displaystyle\hat{\mu}_{i,t}+\sqrt{\frac{2\log(K_{i,t}^{2}/\eta^{2})}{K_{i,t}}}+\frac{\rho_{i}}{K_{i,t}}\geq\hat{\mu}_{i^{\ast},t}+\sqrt{\frac{2\log(K_{i^{\ast},t}^{2}/\eta^{2})}{K_{i^{\ast},t}}}\,.$

By Chernoff-Hoeffding bound and the union bound,

$\displaystyle\quad\mathbb{P}\left(\hat{\mu}_{i,t}-\mu_{i}\geq\sqrt{\frac{2\log(K_{i,t}^{2}/\eta^{2})}{K_{i,t}}}\right)$
$\displaystyle\leq\sum^{t}_{s=1}\mathbb{P}\left(\hat{\mu}_{i,t}-\mu_{i}\geq\sqrt{\frac{2\log(s^{2}/\eta^{2})}{s}},K_{i,t}=s\right)$
$\displaystyle\leq\sum^{t}_{s=1}\mathbb{P}\left(\hat{\mu}_{i,t}-\mu_{i}\geq\sqrt{\frac{2\log(s^{2}/\eta^{2})}{s}}\right)$
$\displaystyle\leq\sum^{t}_{s=1}\frac{\eta^{2}}{s^{2}}=\eta^{2}\sum^{t}_{s=1}\frac{1}{s^{2}}\leq\frac{\pi^{2}}{6}\eta^{2}\,.$

Thus
$\hat{\mu}_{i,t}-\mu_{i}\leq\sqrt{\frac{2\log(K_{i,t}^{2}/\eta^{2})}{K_{i,t}}}$
and similarly
$\mu_{i^{\ast},t}-\hat{\mu}_{i^{\ast}}\leq\sqrt{\frac{2\log(K_{i^{\ast},t}^{2}/\eta^{2})}{K_{i^{\ast},t}}}$,
each with probability of at least $1-\frac{\pi^{2}}{6}\eta^{2}$. Hence with
probability $1-2\frac{\pi^{2}}{6}\eta^{2}$, we have

$\displaystyle\mu_{i}+\sqrt{\frac{2\log(K_{i,t}^{2}/\eta^{2})}{K_{i,t}}}+\frac{\rho_{i}}{K_{i,t}}\geq\mu_{i^{\ast}}\,.$

When arm $i$ is pulled, arm $i$ wants to ensure the following holds

$\displaystyle\sqrt{\frac{2\log(K_{i,t}^{2}/\eta^{2})}{K_{i,t}}}+\frac{\rho_{i}}{K_{i,t}}\geq\delta_{i}\,.$

where $\delta_{i}=\mu_{i^{\ast}}-\mu_{i}$. Then,

$B_{i}\geq\rho_{i}\geq\left(\delta_{i}-\sqrt{\frac{2\log(K_{i,t}^{2}/\eta^{2})}{K_{i,t}}}\right)\cdot
K_{i,t}\,.\qed$