Influential Bandits: Pulling an Arm May Change the Environment
Authors: Ryoma Sato
Shinji Ito
Venue: Accepted by TMLR ()

Abstract: While classical formulations of multi-armed bandit problems assume that each arm's reward is independent and stationary, real-world applications often involve non-stationary environments and interdependencies between arms. In particular, selecting one arm may influence the future rewards of other arms, a scenario not adequately captured by existing models such as rotting bandits or restless bandits. To address this limitation, we propose the influential bandit problem, which models inter-arm interactions through an unknown, symmetric, positive semi-definite interaction matrix that governs the dynamics of arm losses. We formally define this problem and establish two regret lower bounds, including a superlinear $\Omega(T^2 / \log^2 T)$ bound for the standard LCB algorithm (loss minimization version of UCB) and an algorithm-independent $\Omega(T)$ bound, which highlight the inherent difficulty of the setting. We then introduce a new algorithm based on a lower confidence bound (LCB) estimator tailored to the structure of the loss dynamics. Under mild assumptions, our algorithm achieves a regret of $O(KT \log T)$, which is nearly optimal in terms of its dependence on the time horizon. The algorithm is simple to implement and computationally efficient. Empirical evaluations on both synthetic and real-world datasets demonstrate the presence of inter-arm influence and confirm the superior performance of our method compared to conventional bandit algorithms.

Published in Transactions on Machine Learning Research (6/2025)
Influential Bandits:
Pulling an Arm May Change the Environment
Ryoma Sato National Institute of Informatics
rsato@nii.ac..
Shinji Ito
shinfi ac.jp
The University of Tokyo and RIKEN
Reviewed on OpenReview: htips: // openreview. net/ pormfo id- YVKaDfVbb3
Abstract
While classical formulations of multi-armed bandit problems assume that each arm's reward independent and stationary, real-world applications often involve non-stationary environ- ments and interdependencies between arms. In particular, selecting one arm may influence the future rewards of other arms, scenario not adequately captured by existing models such as rotting bandits restless bandits. To address this limitation, we propose the influen- lial bandil problem, which models inter-arm interactions through an unknown, symmetric, positive semi-definite interaction matrir that governs the dynamics arm losses. We for- mally define this problem and establish two regret lower bounds, including superlincar Q(T log"21 T) bound for the standard LCB algorithm (loss minimization version of UCB) and algorithm-inndeeeneen Q(T)) bound, which highlight the inherent diffieulty of the setting. We then introduce estimator tailored to the structure of the loss dynamics. Under mild assumptions, our algo- rithm achieves a regret of (oKTlog 7), which is nearly optimal in terms of its dependence on the time horizon. The algorithm is simple to implement and computationally efficient. Empirical evaluations on both synthetic and real-world datasets demonstrate the presence of inter-arm influence and confirm the superior performance of our method compared to conventional bandit algorithms.
algorithm based on lower confidence bound (LCB)
1 Introduction
The multi-armed bandit problem 7 20 and its extensions serve as fundamental models for merision-mmaing under uncertainty. In such problems, aims to maximize the cumulative reward while simultancously learning the underlying reward model through repeated selection of actions referred to arms and observa- tion of the resulting rewards in environment where the reward distributions are initially unknown. In the most basic setting, it is assumed that the reward for each arm is independently drawn from an unknown, fime-invariant (i.e., stationary) distribution. A variety of algorithms, including Upper Confidence Bound (UCB) 2 19 and Thompson Sampling I 26 have been proposed for this setting, and their effectiveness has been validated both thcoretically and empirically.
In real-world applications, however, rewards are not necessarily stationary and may be influenced by past actions. For example, in recommender systems, arms correspond to items being recommended, and rewards represent user feedback or engagement with those items. Recommending the same item repeatedly may lead to user fatigue, resulting in decreased engagement. Conversely, repeated recommendations could increase a user's interest in the item, thereby enhancing their response over time. To model such dynamics, various models and algorithms have been proposed, including restless bandits 2 29, rotting bandits |1 24 and rising bandits [1. these models, the state transitions for each arm are modeled to depend on the arm selection, and the reward distribution is assumed to vary depending on the state. Other approaches have

---

Published in Transactions on Machine Learning Research (6/2025)
also been explored for instance, the blocking bandit framework 5 0 introduces constraints that prohibit consecutive selections of the same arm, which can be interpreted as way to address reward decay.
One of the key limitations of these existing models lies in the strong assumption that the impact of selecting an arm is confined solely to the reward of that particular arm. Due to this limitation, these models fail to capture scenarios which selecting one arm may influence the future rewards of other arms. In real-world problems, it is rare for the rewards of all arms be completely independent, making it important to consider such interdependenctes. For instance, in the context of recommender systems, recommending particular item (such movie product) and having the user engage with it may reduce their interest in similar items, or conversely, increase their interest in related items.
To overcome this limitation and address scenarios where interactions between arms exist, as described above, we initiate the study of the inftuential bandit problem. We begin by formally defining the influential bandit problem and deriving a lower bound on the regret, thereby highlighting the inherent difficulty of the problem. We then propose an algorithm tailored to this setting and provide a theoretical analysis of its performance. Finally, we validate the proposed model and assess the effectiveness of the algorithm through empirical experiments using synthetic and real-world data.
1.1 Our contribution
In formulating the influential bandit problem, we introduce an interaction matrix E RX to model the influence that selecting one arm has on the rewards of other arms, where K denotes the number of arms. This matrix captures the pairwise interactions between arms, where each element represents the impact of selecting arm i on the loss of arm j. We assumne that the interaction matrix is symmetric and positive semi- definite. The matrix is initially unknown, and addressing the uncertainty in the environment arising from this is critical challenge in this problem. For performance evaluation, we define regret as the difference between the cumulative loss incurred by the algorithm and the cumulative loss of the optimal sequence of actions, assuming full knowledge of both the interaction matrix and the initial loss values.
To illustrate the difficulty of this problem, we present two regret lower bounds. First, we show that the LCB algorithm (loss minimization version of UCB 2), one of the most standard algorithms for the classical stochastic bandit problem, suffers regret of 2(T ( log" T) in the worst case, where T denotes the time horizon. At first glance, superlinear regret in T may appear surprising in the context of traditional bandit problems; however, such behavior is common under the setting considered in this work. Indeed, since each arm selection can influence future losses, the per-round loss can grow as large as O(T), leading to a maximum possible regret of O(T2). Therefore, achieving regret strictly smaller than O(T)) is considered a non-trivial result. As a second lower bound, we show that any algorithm must incur at least. ((T) regret in the worst case. This implies that, from the perspective of worst-case analysis (ignoring constant factors), achieving O(T) regret is optimal.
One of the main contributions of this paper is the proposal and validation of a novel algorithm for the influential bandit problem. The proposed method is based on new lower confidence bound (LCB) estimator that accounts for the structure of the loss dynamics. Under a mild assumption that the noise is bounded, we show that the algorithm achieves a regret of OKT log where K the number of arms and T the time horizon. In comparison with the previously established lower bounds, this result demonstrates that the proposed method outperforms the standard LCB algorithm and is nearly optimal in terms of its dependence on T. Furthermore, the algorithm is easy to implement and computationally efficient, making it practically useful as well.
The effectiveness of the proposed model and algorithm is also evaluated through numerical experiments. First, experiments on synthetic data confirm that the proposed algorithm consistently outperforms the standard LCB algorithm in practice. Next, using a real-world dataset, we verify the presence of inter-arm interactions as modeled in our framework and investigate the specific nature of these interactions. We further demonstrate the superiority of the proposed algorithm through empirical evaluation.
2

---

Published in Transactions on Machine Learning Research (6/2025)
2 Influential Bandits
Let A E _2 be an unobserved interaction matrix, which is positive semi-definite, and 15) E R be the unobserved initial loss for each arm j [K]. We consider the following online learning problem. An algorithm repeatedly chooses arm z(t) [K] at time i, and observes loss (() + <(),, where g(t) is random noise with zero mean and bounded variance. The losses are then updated by
- - + Auny for all j [K].
(1)
The goal is to minimize the regret, which is defined the difference between the total loss of the algorithm and the total loss of the best sequence of actions in hindsight. Note that the benchmark is the best sequence of actions in hindsight, not the best single arm in hindsight. We call this problem the influential bandit problem. The crux of this problem is the interaction matrix A, which typically represents the similarity between arms. When we pull an arm, the expected loss of similar arms increases. For example, in the online advertising problem, repeating the same or similar advertisements may decrease the effectiveness of the advertisements and thus increase the loss. Some elements can be negative, which models the recovery effect. For example, repeating horror movies may lead to fatigue, but sandwiching horror movie between two comedy movies may recover the effectiveness of the horror movie, i.e., Ahorror, horror 0 but Acomedy horror < 0. The influential bandit problem is generalization of the stochastic bandit problem, where the interaction matrix is the mull matrix.
We first show the following fundamental property of the influential bandit problem. Proposition 2.1. Let = Et= e( be the total number of times each arm is chosen, where e()) E ERK is the one-hot vector of arm i. The expected total loss is given by
Σ L (1)
+ 2
1 x
Ax
Ax
1 A1, A22. AKRZæ.
(2)
2
In porticular, the total loss does not depend on the order of the actions.
Proof. The expected loss of arm j at time I is given by
=
Agin
(3)
for all j [K]. The expected total loss is then given by
T
A A000
(4)
200
200
T +-
=
1() x + Σ
10000
(5)
Am
s=1
10) x +
1
ΣΣ
A A
Σ t=1
A A0000
(6)
2
+= t=1
1
(1T x
+
x
Ax
A A22 AKKoæ,
(7)
where (a) follows from the symmetry of A. The last equation shows that the total loss does not depend on the order of the actions but only on the total number times each arm is chosen.
Let (11) AA,, A AKK]T Then, the expected total loss is given by
[(x) = b x +
2 Ax.
(8)
3

---

Published in Transactions on Machine Learning Research (6/2025)
Therefore, the infiuential bandit problem is equivalent to finding the sequence of actions that minimizes the quadratic loss in Eq. 8 in contrast. to the stochastic bandit, problem, where the loss is linear. The challenges lie in the following facts.
Neither b nor A known in advance.
Choices of actions not independent. One action affects the future losses of other actions. The negative effect of an exploratory action may persist over time. We will present an example where one failure choice causes catastrophic consequences in Proposition 2.3
In particular, we cannot arbitrarily choose æ but must sequentially update a +- x + e (( and thus cannot drastically change the optimization variable æ at each time step. This introduces challenge from the optimization perspective.
One of the key distinctions between the influential bandit problem and the stochastic bandit problem lies in the loss scale. Since the influential bandit problem incurs quadratic loss, expecting sublincar regret is unrealistic but subquadratic regret is typical objective, whereas in standard linear bandits, achieving sublinear regret. a typical objective. Indeed, even O(T1.99) regret is non-trivial and the standard lower confidence bound (LCB) algorithm, which corresponds to the upper confidence bound (UCB) algorithm in the reward maximization sctting, cannot achieve this.
Proposition 2.2. There erists an instance of the inftuential bandit problem such that the standard LCB algorilhm, which selects
2 log
(00) arg min iE(K]
As
(9)
ni
and selects the minimomm index when there are lies for all E [T], incurs the regret Ω the empirical mean of the losses of arm i and n, the number of times arm is chosen.
T2 log"
where fag is
We prove the proposition by construction. Notably, the counterexample instance is noiseless. The LCB algorithm fails even in a noiseless environment. the influential bandit problem.
Proof Skelch. The counter example is K = 2, A = [], 2]], (0)) = [1. 1J, and g(0) = 0. There are no noises, and the process deterministic. The optimal sequence of actions is j(t) = for all (T), which incurs the total loss [T(T+1) We can prove that the number of times the LCB algorithm chooses arm 2 at least Q Tng which leads to Ω Ing regret. The key intuition behind the lower bound as follows. Whenever the LCB algorithm selects the optimal arm (arm 1), the losses for both arm 1 and arm are increased by the environment. However, only the loss of arm is actually observed, so the LCB algorithm updates the estimated loss only for arm 1, while the estimate for arm 2 remains unchanged. After pulling arm 1 consecutively for more than about Ollog t) rounds, the LCB score of arm 1 becomes larger than that of arm 2. This guarantecs that arm will be selected at least on the order of log by the LCB algorithm. The complete proof is in Appendix A
In addition, there exists counterexample where the regret must be at least lincar in the time horizon. Proposition 2.3. There erists instance of the infiuential bandit problem such that for any algorithm, the regret is al least Q(T).
Proof. Let = 2. Since initially an algorithm only knows the number arms and no further instanco-specific information, its first action cannot depend on the instance. Suppose the first action

---

Published in Transactions on Machine Learning Research (6/2025)
is (0) = 1. Let
and b -=6))
A
(10)
3
The optimal sequence of actions is (0) for all E [T], which incurs the total loss the best possible sequence of actions after i(1) = 1 is ((() for all t= lotal loss _ + T + - Therefore, the regret at least 7 + = 9(T).
8 7 By contrast, This incurs the
The counterexample above indicates that the influence of an action lasts, and single failure choice may cause catastrophic consequences. If an action increases the loss of other actions by constant, the total regret increases linearly in the time horizon.
We will propose an algorithm that achieves near-optimal regret. Before presenting the algorithm, we intro- duce the following assumption for simplicity.
Assumption 2.4. The maximum absolute value of the interaction matrix A is bounded by 1. Assumption 2.5. The noise g(9) is bounded by 1.
The proposod algorithm is follows.
Algorithm 1: Influential LCB
qi t for all i E [K]
// time passed since the last observation
(1) t- -ox for all E [K]
// last observed loss
for t= L.,,.... T do
(()) t arg min
// lower confidence bound // update the estimate by the observed loss // update the confidence bound
Observe loss (t) = (t)
200 + e())
(1) if i = (())
((++))
(()) otherwise
i ((0)
(1+1) +-
(t)
+1 otherwise
The expected loss an arm decreases by at most one at each time step by Assumption 2.4 If we observe the loss 4 of arm i at time (t - c;), a reasonable lower bound of the loss arm at time t is 4 c - 1. The regret of Algorithm D is given by the following theorem.
Theorem 2.6. The vegrel of Algorilhm 1 is al most
5K +3
2 + 2
T (2K + 21 + +4) = O
(11)
A failure attempt to prove this would be using the relation ((0) CąO 1 ((0) ((0) C(() 2o... where g00s the optimal action at time t, summing over f, using the relation E, C,0 I (K - 1YT, and concluding that the regret E ((0) at most (K- T O(KT). This is not valid because 2000 is the loss
in the very state the algorithm has reached with {()) ((() _..,)...,, ((t-1), but there might be a better sequence
10 ((t) since the choices (1)s "...,;(t-1); that leads smaller loss at time t. The regret is not E, 2 ((e)-
are not independent. We need to avoid independently treating states.
Proof. Let (1), ...., ((T) be the sequence of actions chosen by Algorithm D mumber of times cach arm is chosen up to time and [(x(t)) be the total loss at time t. As the
(+)) be the total
5

---

Published in Transactions on Machine Learning Research (6/2025)
combinatorial problem is cumbersome, we use the continuous solution
x (t)
arg min L(x) =t(AR
(12)
as the benchmark, where tAk = fx E R
x 2 0, 00 = t is the (K - 1)ddiensiinall probability
simplex expanded by ((x(!))) is a lower bound of the total loss mingersknzy L(x:) of the optimal
sequence of actions. Let
p' = arg min
2 Ap
(13)
pEAx
be the optimal distribution of arms that minimizes the quadratic term L2(p) def 11"" Ap. Let p())
=
w(th) be the empirical distribution of arms. We have
p p((+1) (0))_ (((+1)
(())
(14)
t ++1
x01) + (i())))
p
(15)
t t+1 1
tp + (((t))
p(())
(16)
t+1 1
1
(el((t) -p(0) D10).
(17)
++1 1
We then have, by Taylor expansion around p(t),
(2(((t)))= = ))( (L2(p(0)T (plit1) -p())
1
-p(t) (2(2(((1) (p(tt))p((t)
p(()
2
(18)
( (2( T (p(t)))p(0)
1
(p(ttt) - p(o) A (plltt)) (pi(tt)--p()) -p(o)
+
(19)
2
@ ()( + 1+1 g (c(1))-((')
1
)p())=
T A (el((0) -p(() (20)
+
2(t + 1)2
(1) + 1+1 و6
1
(c(it)))p'1 (t + 1)2*
2
(21)
where we define g ()) Ap in (a), (b) follows from Eq. 17 and (c) follows from Assumption 2.4 i.c., | mmxx = maxi5 Aij < 1, and ||e((")) - (011 < 2. Let i' = arg min; Js,
equivalently, e = arg min 9² i.e, elr) is the direction of the Frank- Wolfe update. From
convexity L2.
(e((t) -p'))
min TTpp (p - (0)
(22)
pEAx
min peAx
(C)(p()) + +g (p)) ()
(23)
< C2(p') - ()(
(24)
From the definition of (10))) we have for t t (K++) + 1),
g T (((tt)) (a)
App()) e((r)))
(25)
T 7 (Azel:))
(26)

---

Published in Transactions on Machine Learning Research (6/2025)
(10) + A
elitn))
1 f elto))
(27)
$
1
(10)
Alo(1)
eli(r))
+
(28)
20
1 (iie))
=
(29)
t
t
1 (0)
100 1l00
(30)
200
t
2 1 (no
/
+ 400
+ +1)
(31)
t
(9) 1 (11 + 2010
|1000)100 1100
2 1
c/- + +1)
(1)
(32)
+ +2) || 11:00
(149 + 20
< t
10
(33)
t
(10) + An!
|1(0)) 1o0
e(1*) + +22(10 + 2)
(34)
t
+ 2 + 21
(Aml1)
e(6 + ((9)
+2((t)
(35)
+2) 2l0
g (i)) +
2e (1)
(36)
1
g + 80
(t)
+ 1 + 1100))10)
(37)
where (a) follows from the definition of g: (b) follows from (1))) + c,00 + 1) is an upper bound of the
(t)
expected loss because it increases at most Cate) from the previous observation, the noise is bounded
by 1, and i is set to be the previous observation for t 2 (K + 1), and (c) follows from the algorithm
chooses z(0) such that 2(0) have
6x0 S ( c for all E [K]. By combining Eqs. 21 24 and 37
(t)
we
8(1 1) def (22)) C2(p")
(38)
( S (2 + I+1 g (elito) -p!o)) +
2
- C2(p")
(39)
(1+1)² 1)2
() ()( + t+1 g (cl -p())= + (t+ 11+ 1)2
1
2
+
2
(:0)
(1)
+1+ 110)) 110) - -C(("))
t(t +
(40)
( I () + ++1
(co(D")Cc2(p"))) -c2(p")) +
2
2
+1+ 110001100
C2(p")
-
(t + 1)2
t(t+1) 1)
(41)
1+1
t
- -(2("))
(1 1)2
2
+ 1(t+1) 1)
2
(20))
(t)
+ +1+ + 1101))12))
(42)
2 + 1(t+1) 1) (0i)) + +1 + 1101)))0)
2
8(t)
(43)
1+1 (t+
1)2
where (a) follows from Eq. 21 (b) follows from Eq. 37 and (c) follows from Eq. 24
By multiplying
++1 to both sides and letting 8(1) = 15(1), and recursively applying it from L == [K + 1) to T 1,
5(T) S 8TT - 1) + T T T-i
2 +
2
GT 13 +1 11]))))))))
(T-1)
(44)

---

Published in Transactions on Machine Learning Research (6/2025)
T-1
2
T-1 1
(4) 10)
+ +1+ |1 11
S 8(KK 11) +
Σ
+2
(45)
(s (s+1)
==K+1
== R+
Let ((1) = 0 and Φ(t + 1) = (tt + K. r.
We show Σ.-1
[00
+ 1 E
C 1 (tt) for 2 by
(1)
kE(K]
induction. When 2, 2,
(1)
(2)
(46)
[E[K]
$E[K]
(a)
Σ
c
(47)
KE(K]
(b) K
(48)
(2),
(49)
where (a) follows from e, = 0, and (b) follows from of is incremented by 1. Suppose the induction
cle) ((n)
hypothesis E
==
+
6-1
1 EiE[K] cy2 I (t) holds. Then,
(40)
1 Σ
1++
((0)
1+ Σ
c (++))
(50)
b
iE [K]
ighill)
200
1
1 +
Σ
(1) + (K
1)
220
(51)
t
xE[K]
(1)
(0
1
(1)
K
101)
(52)
t
t
KE|K
K
(0)
(53)
t
KE|K]
20
(1)
K
(54)
8
XE[K]
(b)
K
(())
(55)
2 + 1).
(56)
where (a) follows from the fact that the algorithm increments c(t) by 1 and resets
900 to 1, and (b)
(t)
follows from the induction hypothesis. Since (T) K KT- < K(1 log 7)) and c (t) 0, we have
II-1 (00) < K(1 + log T). Thcrefore,
T-1 Σ
T-1
+ 1 | occ
3(T) < 8(K + +1) +
2
+2
Σ
(00
(57)
(s+1] 1)
*=
#=K+1
< 8(K + 1) + 2 log T + 2K + log T) + 2 log T + 211 m| log T
(58)
< 8(K + 1) + 2K + (2K + +111100 +) logT
(59)
= (K + 1)6(K + 1) + 2K + (2K + 22) + 44 logT
(60)
8

---

Published in Transactions on Machine Learning Research (6/2025)
< (K + 1) (Lo(p(kt)) - L2(0") + 2K + (2+ +111 1100 + +4) log
(61)
(2)
(K + 1) + +2 + (2K + 21 || +4) logT
(62)
K+1
p
(K+IITT Ap (K+K)) = 2K + (2K + 11 4) log T
(63)
2
K+1
+ +2K + (2K + 2/1(()) 1loo + 4) log
(64)
2
5K +1
+ (2K + 1| + 4) log T,
(65)
2
where (a) follows from A is positive semi-definite and (2(p") 2 O. Since ö(T) Tō((),
5K -
+ 2K + 1110 + +1) log T
- S
(66)
2T
T
Therefore, the regret is
1
((x(T)) ((x(2))) =b bTx (T)
(T)
-b= -
[ (x(T)
(67)
1 (T)T Ax
1
(T)TT (T) + +2T bl100
(68)
2
2
T
T (T!-T
(T))
2 P
(T) Ap!
A
(69)
2
T
T
(a) T
T
5
P (TI Ap
2 pp' T Ap" + 27 b
(70)
2
(T) (2(1")) + +2T(lbllo
(71)
(5K + +JT
+ +(2 + 22| + 44 Tlog + 2T
(72)
2 (5K + 1)T
(
+ (2K 21111 + 4) T Tlog T + 2T | 1100000000
1
(73)
2)
5K +3
+ 11 T (2K + 111 + 4) T TlogT
(74)
O(KTlggg log
(75)
where (a) follows from (T)- AK, and (b) follows from b = ((1) 1A A22 ................................ AKK]T.
We believe that this analysis is of independent interest. The gradient of the objective function is vl(x(()) = b Az(() ((t) + Const. When apply the Frank- Wolfe algorithm g 16 22 to this problem, the update is the form of (1+1) + Bel where e
(1fe) waan = arg min ()) p is the Frank-Wolfe update, and since the optimization domain is the simplex and the lincarized function achieves ,(t)
arg min; (b Aat arg min; (109) + Const), the arm that minimizes the gradient. The key insight is here.
the minimum at the corner of the simplex, "Frank-Wolf Wolf arg min; (VL(a())))
The Frank-Wolfe update on the simplex domain
Selection of one corner of the simplex
= Selection of one arm.
Therefore, the Frank- Wolf algorithm sequentially chooses the arm that minimizes the gradient (or the current loss) and inserts into the current state. This behavior similar to the influential LCB algorithm. We exploited this connection and applied the convergence analysis of the Frank- Wolfe algorithm the influential LCB algorithm.
9

---

Published in Transactions on Machine Learning Research (6/2025)
Remark (Assumption the Norm of A). The assumption | maxij |Aiyl < 1 is not necessary for the influential LCB algorithm and the regret analysis. Alternatively, if we know the scale of rewards in advance, we can normalize the rewards accordingly. When we know that || S B, lower bound of the loss is 4 Bes, and the influential LCB algorithm chooses the arm that minimizes the lower bound in Line 4. When we have no prior knowledge of the norm of A, it can be estimated in the initial phase of the algorithm. If ((() g(t+1) J. (() (10) g(t) and [(++1) zf(t1) + g((++) 110 A (
Thus, As def If (()) = j(++2) = j and g(++1) = k, Ays def (t+2) L( AS = A + Ast + g(t+2) - g0)) Aرs is a noisy estimate of A₁k with at most a constant error. Therefore, with O(K2) samples, we can estimate with a constant error. The same analysis as Theorem 2.6 is valid for these cases.
= ((+l) ((0 Ass +g(++) -(()) is a noisy estimate of As with at most a constant error.
3 Related Work
The resiless bundit [25 29 rolling bundit [21] 24 and rising bandil problems [4] are particularly closely related to this work. In these settings, each arm is associated with a state that evolves depending on whether the arm is selected, and the reward distribution varies according to the current state. In the rotting bandit model, is assumed that the reward of a selected arm decays over time, whereas in the rising bandit, the reward increases. The restless bandit further generalizes this setting by allowing the states and hence the rewards of unselected arms to evolve according to different dynamic. However, a key distinction from our model is that in these frameworks, the state of cach arm depends only its own selection history. In contrast, the influential bandit problem considers interdependencies, where selecting one arm can directly affect the future losses of other arms. On the other hand, those prior models allow for non-linear reward dynamics, so our setting is not necessarily more general in all aspects. Notably, the recently proposed graph- triggered rising bandit problem [ also models interactions across arms, where selecting one arm can infiuence the state of others. While similar in spirit, it differs from our model in assuming monotonic non-decreasing rewards and restricting interactions based on an underlying graph structure. Our model supports general interactions modeled by an interaction matrix and can handle both increases and decreases in rewards.
Our model can also be interpreted within the framework of a Markov Decision Process (MDP) or a Partially Observable MDP (POMDP). For example, if we define the system state at each time step as the vector of selection counts for all arms, then the state transitions deterministically according to the chosen arm, and the reward can be modeled as a (possibly unknown) stochastic function of the state and selected action. In this sense, the problem can be viewed as an instance of an MDP. One might therefore consider applying online learning algorithms designed for MDPs. However, to the best of our knowledge, existing algorithmss are not directly applicable to our setting. Most online MDP algorithms have been developed for the epésodic setting, where learning occurs over finite-horizon episodes that restart from initial state, such as in 3 This setting differs significantly from ours, which operates in non-episodic, continual learning framework.
3440 15 [77 [[]]
these typically rely on assumptions such as bounded state spaces or ergodicity/ /ixxng conditions on the state transitions,
Although there are some studies on the infinite-horizon average reward model 2 27 28
is also a general framework capable of handling state transitions and uncertainty; however, approaches in this research area typically focus on continuous variables and often rely on assumptions such as stabilizability controllability, making them not directly applicable to our problem setting.
which do not hold in our setting. Online control 10 13
4 Experiments
We validate the effectiveness of influential bandits through numerical experiments.
4.1
Regret Analysis
We confirm that the regret of Algorithm 1 is near-linear (Theorem 2.6 while the standard LCB algorithm
incurs near-quadratic regret (Proposition 2.2
10

---

Published in Transactions on Machine Learning Research (6/2025)
10'
Standard LCB
Standard
Regret (log scale)
106
Influential LCB
Standard LCB Fit (slope=1.73)
Regret (log scale)
10
Infiuential
Standard (slope=1..2)
105
Influential LCB Fit (slope=1.02)
105
Influential (slope-
10
10a
10a
10
10
10
10-1
100
10
10
10a
10
10
10
10
10.
10
10
10
Round (log scale)
Round (log scale)
(a) Counterxxampe Proposition
2.2
(b) Random instances.
Figure 1: Regret Analysis. The x-axis the time horizon in log scale, and the y-axis the regret log scale. We fit linear regression lines to the log-log plot. (a) The slope of the fit line 1.02 for the influential LCB algorithm and 1.73 for the standard LCB algorithm. The former converges to 1 and the latter converges to 2 as T' increases. This validates that the standard LCB algorithm incurs near-quadratic regret in the worst case. (b) The slope of the fit line is 1.14 for the influential LCB algorithm and 1.72 for the standard LCB algorithm. This case also shows that the rate of the regret of the influential LCB algorit is kept near-linear while the standard LCB algorithm can be large even in the average case.
We use two settings. The first setting is the same as the counterexample in Proposition 2.2 i.e., K 2, [[1, 1], [1. 2]] (0)) = [], e(t) = 0. The optimal sequence of actions is {(() = for all E [T), and the total loss is ŞT(T + 1). Figure (a) shows that the growth rate of the regret of the influential LCB algorithm is near-linear, while the standard LCB algorithm incurs a near-quadratic regret.
The second setting uses random instances with matrices A by sampling the entries of B R from the standard normal distribution and setting B
arms. We generate random semi-positivv definite
A max,, B Bi.," z(1) E RK is sampled from the standard normal distribution. The noise e,¹) is sampled from the standard normal distribution. Since the optimal sequence of actions is unknown, we use the continuous relaxation L = min b x fo=" Aæ as the benchmark, which is provable lower bound of the expected total loss. We define the difference between the expected loss Σ go of algorithm choices j(1) ((T and the benchmark score L' the regret. We run the experiments with 100 seeds and Figure (b) reports the average regret. The result shows that the growth rate of the regret of the influential LCB algorithm is kept near-linear, while the standard LCB algorithm incurs a near-quadratic regret even in random instances.
4.2 Model Analysis
We confirm that pulling an arm can indeed change the losses of arms and validate the model of influential bandits with real data. We use MovieLens-32M dataset [2]. We view each user as solving a multi-armed bandit problem, treating each user as an independent instance. A user selects a movie, watches it, and the user's preference is revealed as the loss. Since there are too many movies, and each user selects a movie al most once, we consider a movie genre an arm rather than an individual movie. Therefore K #genres 20. Since movie can have multiple genres, we randomly select genre of movie and assign it to the movic. We define the loss as (5 rating) since the 5-star rating is recorded in this dataset. The history of genre selections and ratings defines log data of a bandit problem.
To examine whether the assumption of stationary losses or the assumption of influential bandits more appropriate, we evaluate how well each model predicts future losses. We use a leave-onc-out validation approach. Specifically, we sort each user's history in chronological order and fit the model using all but the last rating. The final rating is then predicted using the trained model.
11

---

Published in Transactions on Machine Learning Research (6/2025)
Horror
10-4
Documentary
Film Noir
Musical
1.2 x 10
Western
Animation
1,0 x 10"4
Mystery
Thrille
35
Drama
0.8 10"*
Romance
30
Adventure
Action
0.5 10"4
Fantasy
Frequency
25
Comedy
0.3 10
20-
So
Children
10"4
15
(no genres listed)
IMAX
War
-0,2 10"*
10
Horror
Documiettry na
Film-Noi
Musical
Western
illmationn
Thriller
Drems
Romance
Action
Adventure
Fanlasy
Comedy
Crime
So
Childre
Wer
MAX
(no genres listedy
5
-7
-6
-
-4
-3
-2
1og10 ([AlIF)
(a) Distribution of the norm of A.
(b) Estimated interaction matrix.
Figure 2: Model Analysis. (a) The distribution of the norm of A. The majority of users have norm greater than 10-1, which implies the existence of interaction among arms. However, there are some users with almost zero norms, which indicates that the positive semi-definite interaction not valid for these users. (b) The averaged interaction matrix A as a heatmap. The diagonal elements, such as horror and comody, are high, which indicates that consecutively watching similar movies increases fatigue, The off-diagonal elements, such those between horror and comedy, are negative, indicating that watching comedy movie helps recover from the fatigue caused by watching a horror movie.
Under the assumption of stationary losses, we estimate the mean loss for each genre (arm) based on the training data and predict the loss of the last chosen genre using this mean value. In contrast, the influential bandits model assumes that ((t) x (a)) + Ax and we fit ((2) E g. and E kxx to the data. Since A is positive semi-definite, we rewrite the model ((t) (()) + BB"T x(t) and optimize ((!) and E kx parameters. The number of parameters estimate is thus (K+K3) 420. We minimize the squared error between the observed values and the predicted values using gradient descent with momentum. Finally, we use the obtained (2) and A to predict the loss for the last selection.
To ensure sufficient training data, we consider only users with at least 4096 data points, resulting in = 73 valid users. We conducted experiments for each user. The mean squared error (MSE) for predicting the final loss was 0.6156 0.9775 under the stationary loss assumption and 0.5720 + 0.8238 under the influential bandits assumption. The influential bandits model achieved better predictive accuracy, suggesting that losses are not stationary. should be noted that the difference is statistically significant since the ratings are highly noisy to predict.
To further examine the validity of the assumptions, we analyze the estimated A. First, Figure 2 (a) presents the distribution of the norms of the estimated A. Each sample corresponds to a single user. The majority of users have a norm greater than 10 and there are 20 users with a norm exceeding 10-3, 3, This indicates that some users exhibit strong interactions. On the other hand, 7 users have norms below 10-5, and the estimated interaction matrix is almost zero, suggesting that for these users, the assumed positive-dcfinito interaction, where watching similar movies increases loss (i.e., "fatigue"), not observed. Instead, there may even be "reinforcement" effect where watching similar movies reduces loss. We further discuss this phenomenon in Section 5.1 These findings suggest that the validity of the influential bandits assumption depends on the user and the environment, but there are indeed cases where the influential bandits model is reasonable.
Next, we visualize the averaged interaction matrix A as a heatmap in Figure (b). Notably, A Horror and AComedy,Comedy Comedy exhibit significantly high values. This suggests that watching horror movies consocutively comedy movies consecutively leads to increased losses (i.e., decreased ratings). Additionally, A Attorror,Comooty Comedy
12

---

Published in Transactions on Machine Learning Research (6/2025)
25
1000
20
800-
Frequency
Frequency
15
600-
10
5
0
3.4
-3.2
-3.0
-2.8
-2.6
-2.4
-2.2
-0.0020
-2.0015 -0.0010 -0.0005
0,0000
00010 0.0115 6.025
l0g10 ([[]]F)
Eigenvalue
(a) Distribution of the norm of A when A is not required to be positive semi-definite.
(b) Distribution of the eigenvalues of A when A is not required to be positive semi-definite.
Figure 3: indefinite Version. (a) The distribution of the norms of A when A is not required to be positive semi-definile. All users have norms greater than 10-1 This suggests that negalive eigenvalues are required to model some users. (b) The distribution of the eigenvalues of A. More than half of the eigenvalues are positive, which validates our positive semi-definite and "fatigue" assumption, but there are many negative eigenvalues as well. This suggests that there are "reinforcement" " effects where watching similar movies reduces loss by, e.g., gaining further knowledge and interest in the genre.
is negative, implying that watching comody movic reduces the loss of horror movics, suggesting that watching horror movie after comedy movie enhances enjoyment. Furthermore, we observe weak positive clusters among (Action, Adventure, Fantasy) and (Mystery, Thriller, Drama, Romance), indicating that watching one of these genres increases fatigue toward other similar genres as well. These effects align with intuitive expectations and support the validity of the influential bandits model.
5
Discussions
5.1
Limitation: Positive Semi-Definite Interaction Matrix
We have assumed that the interaction matrix A is positive semi-definite. This is reasonable because repeating the same action increases the loss in many scenarios, and we partially validated this assumption in Section 4.2 However, this assumption may not. always hold as we observed Section 4.2, We conducted the experiments with MovieLens-32M1 dataset without the positive semi-definite constraint on A. Specifically, parameterize A as A = M M where M R RK* is free parameter and fit z(1) and M to the data with the same leave-one-out validation approach. The mean squared error (MSE) for predicting the final loss is 0.5655 + 0.81 1911,, which is slightly better than the positive semi-definite version. Figure (a) shows the distribution of the norms of A. Whereas some users have almost zero norms in the positive semi-definite version, all users have norms greater than 10-4 4 in the indefinite version. This suggests that negative eigenvalues are required to model some users. Figure (b) shows the distribution of the eigenvalues of A. There are #uscrs x K eigenvalues. More than half of the cigenvalues are positive, which validato our positive semi-definite and "fatigue" assumption, but there are many negative eigenvalues well. This also suggests that there are "reinforcement" effects where watching similar movies reduces loss by, e.g., gaining further knowledge and interest in the genre.
Our framework can be applied to this indefinite version as well. However, the challenge is establishing the theoretical guarantee. The positive semi-definite version framed as an online convex minimization problem. The indefinite version is not convex. The indefinite quadratic optimization problem NP-hard general even the offline case 23 Therefore, the online bandit case is intractable in general. It an interesting future work to formulate tractable setting that can capture the reinforcement effect.
13

---

Published in Transactions on Machine Learning Research (6/2025)
5.2 Limitation: Performance in Small Horizons
The primary goal of this paper was to propose simple algorithm with asymplotically good theorelical performance. The proposed Algorithm is remarkably simple while achieving near-optimal asymptotic performance, as shown in Proposition 2.3 and Theorem 2.6] Thanks to the absence bells and whistlos, it highlights the essence the proposed influential bandit framework. However, this simplicity may come at the cost. of suboptimal performance in finite-time settings. Indeed, Figure 1 (b), the proposed method underperforms the standard LCB algorithm when T 10
The proposed Algorithm adopts highly conservative assumption that A may decrease the loss by 1. In reality, A can be estimated with some accuracy using past data. Specifically, as performed in Section 4.2 we can fit ((1) and A to the past arm selection history and observed loss data. Using the estimated A, we can obtain a tighter lower bound on the current loss, which expected to improve performance in finite-time settings. To advance real-world applications, studying techniques to improve finite-time performance, in addition to ensuring asymptotic performance, would be beneficial.
5.3 Sublinear Regret
As shown in Proposition 2.3 achieving sublinear regret is not generally possible. In some tasks, however, linear regret may not be acceptable. In the counterexample provided Proposition 2.3 there exists an arm whose selection leads to irreversible consequences. However, such arms may not exist. in practical settings. Tn reality, an arm's i loss may recover over time, making it feasible to select it again. In such cases, the optimal strategy may exhibit cycle-like pattern, where all arms are pulled at a certain frequency. This implics even bad choices can be made up for in certain frequency and past mistakes may have only a limited long-term impact, suggesting that sublincar regret might be achievable.
In the experiments on random instances Section 4.1 the influential LCB method typically exhib- ited approximately linear regret average, whereas the standard LCB method suffered approximately quadratic regret. However, in some instances, in- fluential LCB achieved regret lower than the linear
40
Standard LCB Slopes Infiuential LCB Slopes
35-
Frequency
30
25
rate. We fit a linear regression line to the log-log plot of each random instance and calculated the slope of the line. Figure | shows the histogram of the slopes. There are two clusters. The majority of in- stances (61 out of 100) exhibit slope close to 1, but 39 instances exhibit slope close to zero. This suggests that there are "easy" instances where the regret grows sublinearly (e.g., O(log T)). Identify- ing such cases and designing effective algorithms to exploit them remains an important open problem.
20
15
10
5-
0
-0.5
0.0
0.5
1.0
1.5
2.0
Slope
Figure 4: Histogram of the slopes of the regret in ran- dom instances.
6 Conclusion
In this paper, we made the following contributions.
We introduced a new problem setting, influential bandits, where the loss of an arm influenced by the previous selections of all arms (Section 2
We showed thcoretical propertics of influential bandits.
We showed that the regret of the standard LCB algorithm is near-quadratic in the worst case (Proposition 2.2
We showed that there exists an instance where the regret of any algorithm is least linear (Proposition
2.3
14

---

Published in Transactions on Machine Learning Research (6/2025)
We proposed a simple algorithm, influential LCB, that achieves near-optimal regret in the worst case (Algorithm
[ Theorem 2.6
We empirically validated the influential bandits framework and the influential LCB algorithm through experiments (Sections 4.1 4.2)
We confirmed that the regret of the proposed algorithm almost linear in the counterexample and random instances, while the standard LCB algorithm incurs a ncar-quadratic regret even in the average case (Section 4.1).
We confirmed that the loss of an arm be influenced by the previous selections, and the
influential bandits model caplures this phenomenon reasonably well with real data (Section
4.2
We believe that this work introduces new research direction for handling the influence of past actions in a theoretically sound manner. We hope that our work will inspire further research in this area.
References
[1] S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39 JMLR Workshop and Conference Proceedings, 2012.
[2] P. Auer, N. Learn., 47(2-3):235 256, 2002.
and P. Fischer. Finite-time analysis the multiarmed bandit problem. Mach.
[3] M. G. Azar, 1. Osband, and R.. Munos. Minimax regret bounds for reinforcement learning. In Interna- tional conference on machine learning, pages 263 272. PMLR, 2017.
[4] P. Bartlett and A. Tewari. Regal: regularization based algorithm for reinforcement learning in weakly communicating mdps. In Uncertainty in Arlificial Intelligence: Proceedings of the 25th Conference, pages 35 42. AUAI Press, 2009.
[5] S. Basu, R. Sen, S. Sanghavi, and S. Shakkottai. Blocking bandits. Advances in Neural Information Processing Systems, 32, 2019.
[6] S. Basu, O. Papadigenopoulos, C. Caramanis, and S. Shakkottai. Contextual blocking bandits. In International Conference on Artificial Intelligence and Statistics, pages 271 279. PMLR, 2021.
[7] S. Bubeck, N. Cesa-Bia Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trendo0 Machine Learning, 5(1):1 2012.
[8] M. Frank, P. Wolfe, et al. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):05- 1956.
[9] G. Genalti, M. Mussi, N. Gatti, M. Restelli, M. Castiglioni, and A. M. Metelli. Graph-triggered rising bandits. In Forty-forst International Conference on Machine Learning. 2024.
100] P. Gradu, J. Hallman, and F. Hazan. Non-stochastic control with bandit. feedback. Advances in Newral Information Processing Systems, 33:10764-10774, 2020.
[11] B. Hao, N. Lazic, Abbasi Yadkori, Joulani, and C. Szepesvári. Adaptive approximate policy iteration. In International Conference on Artificial Intelligence and Statisties, pages 523-531. PMLR, 2021.
[12] F. M. Harper and J. A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 1(4):19:1-19:1,, 2016. URL http::://doi..rg///// 114/1/227114//277777
[13] E. Hazan and K. Singh. Introduction to online control. arXiv preprinl arXim:221 1.09619, 2025.
[14] H. Heidari, M. J. Kearns, and A. Roth. Tight policy regret bounds for improving and decaying bandits.
In IJCAI, pages 1562 1570, 2016.
[15] P. Hu, Chen, and L. Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference Machine Learning, pages 8971-9019. PMLR, 2022.
15

---

Published in Transactions on Machine Learning Research (6/2025)
[16] M. Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference Machine Learning, ICML, volume 28, pages 427-435 2013.
[17] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. The Journal of Machine Learning Research, 11:1563 1600, 2010.
[18] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-lcarning provably efficient? Advances in Neural Information Processing Systems, 2018:4863 4873, 2018.
[19] T. L. Lai and H. Robbins. Asymplotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1 6(1):433 3:44)2222 1985.
[0] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[1] N. Levine, K. Crammer, and S. Mannor. Rotting bandits. Advances in neural information processing systems, 30, 2017.
[2 S. Pokutta. The frank-wolfe algorithm: a short introduction. arXiv, 2023. URL
bttps://arxiv.org
abs/2311.0531
[23]
S. Sahni. Computationally related problems. SIAM Journal on computing, 3(4):262-25) 279, 1974.
[24] J. Seznec, A. Locatelli, A. Carpentier, A. Lazaric, and M. Valko. Rotting bandits are no harder than
stochastic ones. In The 22nd International Conference on Artificial Intelligence and Statislics, pages
2564-2572. PMLR, 2019.
[25] C. Tekin and M. Liu. Online learning of rested and restless bandits. IEEE Transactions on Information Theory, 58(8):5588 5611, 2012.
[26] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, (5(3/4)2285 1933.
[27] C.-Y. Wei, M. J. Jahromi, H. Luo, H. Sharma, and R. Jain. Model-free reinforcement. learning in infinito-horizon average-roward markov decision processes. In International conference on machine learning, pages 10170 10180. PMLR, 2020.
[28] C.-Y. Wei, M. J. Jahromi, H. Luo, and R. Jain. Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 3007 3015. PMLR, 2021.
[29] P. Whittle, Restless bandits: Activity allocation in a changing world. Journal of applied probability, 25 (A):287-298, 1988.
A Proof of Proposition 2.2
Proof. Let K 2, A- [1, (()) [1, and ((t) 0. There are no noises, and the process is deterministic. The optimal sequence of actions is ((t) = for all [T], which incurs the total loss IT( + 1). Let L(t) ((t) be the loss observed at time t. Let nt(t) be the number of times arm i is chosen the beginning of time Let (t(t) {tf)) (t) (() mn be the set of times when arm i chosen up to time t. As the loss of the first arm increases by one, 1(() = holds. The loss of the second arm is 2
12
(C 1 n1( 2t2(t) f + (2))). Let S,(1) En T((())) be the total loss of arm at the beginning of
S.(0) time t. The empirical mean of the losses of arm is then given by fa ((
(1) (t)
(76)
ni (1)
(1)
(77)
n2 (t)
1
(78)
(t)
16

---

Published in Transactions on Machine Learning Research (6/2025)
(79)
11 (1)
na(t)
Σ k
Σ k
(80)
71 (1)
A=1
t(t 1 1) (22()) + +1)
(81)
ni (t)
2
2
(n2(t) + (t) + ())((t) + +n((t)) (2(()(2((t) + +1
(82)
ni
2
2
(n2(t)² + 2m2(()) (t) + (t)2 + +12(1) + m1())= -=2(t) - (t)
(83)
2m)(1)
1
(2nz(t)n1()) (t) + (t) + (t))
(84)
(t)(t)
1
(2mz(t) + +m1(t) 1)
(85)
2
1
(t + (t))))
(86)
2
1
(1 1 nz(()
(87)
2
(88)
where (a) follows from 2,00 30 1, and
nz(t)
(1)
1
Σ (92)
(89)
ni (1)
j=1
nz(1)
1
2 (t)
Σ k))
(90)
k=1
(
k
(91)
(t(
1
(t - n22(t) (t-(tt - 1)
(92)
ni(1) (t)
2
1
(1 - (2()))( (1)
(93)
n1 (t)
2
(2
= 2
(94)
t
(95)
and thus,
t - (1- n2(()
< $ (1+ nz(()
S si((()
(96)
2
2
We prove that (80 < 20n 2oglog n when 2 19. (12) 98 and (/ 105 < 20 19 log 19 1118.88 .... Suppose
that 1= (2) < 20n logn for some n 2 19. Let L' be the largest index such that iz = 1 and l' < L. Since arm
is chosen at time t',
2 2log t' (2((e))
2 2log t' ni mi("")
Ai S pa((!)
(97)
V
V
17

---

Published in Transactions on Machine Learning Research (6/2025)
2 llogt' n (1)
- (t2 + V
(98)
@ 12(())+ +
2 log 1 V (t) 1
(99)
2 logt t V (t) -1
1 sAa(t)+ +
(100)
2 2oot 11(11 -1
P2(t) +
(101)
where (a) follows from the fact that arm is chosen at time t' and not chosen from time t' + 1 to t and (t) ni (t') + 1, and (b) follows from the fact that the losses are monotonic incrcasing in t, and the
empirical means are also monotonic increasing in t. Since Pr (t') is not updated from time t' + 1 to t,
(t( -1' +
(102)
Si(t) + L(t)
(103)
11((") +1
m1(t')a (t') + L(t')
(104)
mi(t'+ +1
L(t)
SAi(') (1(t") +
(105)
-A((') M(()
(106)
(t)t)
=A1())
(107)
(1)
S (()(()+
(108)
ni(1 (t)
S sA(())
(109)
ni (t) -1
t (t) -1 1 1t -
2 21og 1
s Si2(1) +
(110)
t
S (tt(t) +
(1( -1 1 +
(111)
(1(()= -1
t
P2( +
+
(112)
V
t n2 (t) -2
2
t (t 2
Pe(t+ + 1) S2(t) + L(t)
(113)
(t(() +1
(1) + L(l)
(114)
(t(()) +1
(12(1) + (1) + T.(1)= - (z(()
(115)
(t) +1
= -12(() + L(t) pp((t)
(116)
(2(()) +1
(a)
< (t) + L(t) (t)(t)
(117)
(t)
18

---

Published in Transactions on Machine Learning Research (6/2025)
-2(()) ++ n2()) - (t)
(118)
n2(()
++ (z()) - (t) + V m--2(1)-2 + 1-mz(()-2
(b)
I A2((t) +
(119)
(2(
1+22( - [t(t n2((t) + V m 1-
s12(() +
(120)
(2
1
3
(ー 2
2-
= =p2(() +
+
+
(121)
(t)
2
(t
t
3
t
t
(t2(t) + (1)
+
+
n2(())t n2(() -2) + n2(()(t - (t 2)
(122)
2
/n2(t)
t S (p2(t) + (tz(t)
3
t
t
+
2
+
V
n2(1)(t
n2(() -2) + n2(t)(t (t) 2)
(123)
10)
3 (2(()) + 2n (t)
1
+
2
+
V
t
1-3
3
--3 3
1
(124)
3
5
5
s (t2(() + (t)
+
(125)
2
4
1
S (2(()
+ (t)
+
(126)
where (a) follows from the fact that the loss is monotone increasing and L(t) 2 Po²(),, (b) follows from
Eq. 112 and (c) follows from the fact that m(t-n-2) (1 S S t 3) is minimized when n 1. Suppose
i(++1) ((++2)
g(++))= 1. Then, for k I,..., K,
+1(++++1) = (t + p) (t + k)) + L( + A)
(127)
n1(1 + k) +
= -1 + B) + L(L + k) - Pa (1 + kk
(128)
ni (t + k) + 1
( (i + k) +
L(t + k) - Pa + k)
(129)
1 k t+ k Aua + k)
-A k) +
(130)
1 k
t k: [t + k + n2 (t + k))
2 ml +k)
(131)
8+
1
nz(t + k:)
=Ai(1+ + k)
+
(132)
2
t+
1
n2(() +1
= fi + k)
+
(133)
2
2
t K
1
(2(()) +1
2 (m((+
(134)
t
(1
1
(2 +1
2 21(1+
(135)
2
t
where (a) follows from the fact that the loss monotone incrcasing and L(t+k)= 2 (t(++)) and n1 n1(++1 1)++ <
+ k. At time L + K + 1, the difference of the LCB scores is
LCB K 1) LCBB(t 1))
(136)
2 2log(t + K +K+1) nill + K+1)
(DaLL+K+I)V
2 log(t + K + 1)
[i(++++1)) -
(137)
n2(1 + K +1)
19

---

Published in Transactions on Machine Learning Research (6/2025)
2oog(t + K +1
2 A1 + K 1) V
A2ltt K I+)
(138)
n1 K K+
1log(l + K +1
= mi + K + 1) (1) + (1( -V n1(t+ K K+ (1
+ K +1) - -az(1)) - (22(1)
(139)
2K K
1
(2 +
+ (1)
2 + K +1)
t
+ +4) (12(1)
(140)
2
1.
V ml( K +1)
2mz(1)
1
n2(() +
2 2lgg( + K 11)
2 K
+
(141)
2
(t 111++00 11)
(1)
2 logt
2logt n2(()
log (t(
log 122(t)
+ (1)(t)
-ee(t) +
+V
(142)
Tu (t)
1
1
(2 +
2 log + K + 1)
2 logt t ni
2 2 t V n2((1)
K
(143)
6
mi (1 (1
K 1)
1
m2(() +
1
2log
2 log(1 K +1)
2 2oo
K
+4)
(144)
2
2
t
(tz(t)
V
(t(
n1 + K + +1)
n2((t)
1
(2 +1
+4) + V (t(
2logt
log K +1)
2logt
= K
(145)
2
2
t
(t)
(1(() + K
n2((t)
Here,
2 logt
log(( + K 1)
2
(1z) KK) n2 (t) log(t + K + 1))
(146)
71 (t)
ni (f) + K
ni (t)((n)) K)
2
(1+
K
logl-logh K + +11
(147)
n1 (1) + K
n1
2
(1+ K
log - log(t K +1)
(148)
n1 (t) + K
2
tl+ 4
log
(149)
n1(t) + K
t + K +
log!
2
t exp
+ + log
(150)
#1 (1) + K
2
1(1 + logg
log
i
(151)
(t(t) + K
t K +
2
K logt t log
(152)
(1)
+
K
1+ K +1
2
t 2K { K +1
log
(153)
(t(()
+ K
2
log
(154)
(1(()
+
0,
(155)
where (a) follows from exp(x) > 1 + and (b) follows from K 2 1 and logt 2 2. Therefore,
1 1
n2(()
no
(t)
+1)
(20550) + +a)-
t
2logt t n2(()
LCB + + LCB. LCB K +1) > K
(156)
2 2
222(1)
Here, we consider two cases.
20

---

Published in Transactions on Machine Learning Research (6/2025)
Case 1: 1= (22 < 10m2(().
1
(t( + + - (2me(() + +4) - V (12
2 log
(157)
3
2
2
b
(1)
//
1
n2(1)= +1)
10nz(1)
2 log (1))(())
+ (t)
(158)
3
2
2
nt
1/1
1
1
n2(1)= + 1
log 10 + 2 log no2
9
(159)
3 2
2
(t)
1/1
1 n2(1) +
VI+1
(160)
3 (
2
2
1 (t( +
11
(161)
3
2
2
1
1
1
1
1 - (1)
(162)
2
2
t
N8
1
1
t - 86
- 11
(163)
3
2
2
t
43
11
(164)
3
43
11
(165)
> 0,
(166)
where (a) follows from n1(t)= 2 ni (t(2)) = 86. Therefore, the LCB algorithm chooses arm at time at most
(2) ++ +1 (t + +1 20(nz(t) + 1) log(n2(t) +).
40
(167)
m0++1
Case 2: 1= (22 (0))
(t)
t
+
19
2
1
(t
t
+
2mz(t)
t
44
V
2 log (22(t)
(168)
19
1
1
19ng(t)
19
t
2 logt n2(()
+
+
(169)
(t)
2
2
712
2t
2t
(tz
19
1
19mz(t)
2log T22(t)
2 (t)
+
+4
(170)
2
2
71
20n
(t)
19
1
19
19
1
+ +4) +4)-1
2 2log 122(t)
+
(171)
(t)
2
2
71
20
2t
2nz(t)
19
1
1
19
19
2 log t (22
2 2nz (t)
+
+4
(172)
2
2
19
20
2 . 105
(1)
2 log t
1
+7
+4
(173)
(1)
(1)
V
(1)
2log L nz())
=3 3 V
(174)
llgg log nz))))
23 3
(175)
n2 n2((t)
21

---

Published in Transactions on Machine Learning Research (6/2025)
2log 20 + log (2( + 2 log log n2())
23
(176)
n2((t
23 3 V1+1+1
(177)
>0
(178)
Therefore, the LCB algorithm chooses arm 1 at time at most
-2(()+1 St
(2)
(t) 19
(179)
20n (t) log (t) + 20 log (t) + 20
(180)
(t) log (t) + 20 log (2()) + 20
(181)
(t) + 1) log n2 + 20
(182)
20(n2(t) + 1) log(n2 + 1) 20(n2(t) 1) log(n2 + 1) + (0(n2(t) + 1) log n2 + 20
(183)
(t) + 1) log(n2 + 1) - 20( + 1) log
1
20
(184)
(a)
I (0(n2(t) + 1) log(n2 + 1) - 20(n2(t) +1
(2]
20
(185)
+ (1)
20(m2(1) 1) log(n2 1) 20(n((1) +1
122 (t) +1 20
(186)
(f) log( (22 1) 20 20
(187)
2t) + log + 1).
(188)
where (a) follows from the fact that log(1 x)) 14z (Vr 0).
Therefore, (22) m2(())+1 20(nz(t) log(nz + 1) holds for both cases, and we have proved that t 20m log
when n 2 19. Therefore, ( 20n logn s 20n ( and thus n2((1) 2 20loge The loss of the LCB
algorithm at lest
2 n (t)² (1) An (f))2((t)) + 1 nz(t)² )z(t)²Azz Azz + n1( (1t) - A11) + na(()
1
(110) A22
(189)
= (It2 + (1((t)22()) + n2( (t)
(190)
2
2 (t)² + (t) + (t)²
(191)
t
t
t
t
(192)
20
20 logt
20 log
20 log
1,
t
22
2
t2
t2
(193)
20 logt
800 log t 20g
400 log t
400 t
2
= 2 +
(194)
800
Since the loss of the optimal action is fe(( + 1), the regret is 800
1/
1²
Ing
22


Reviews:
[{"review_id": "NipRSYdInN", "reviewer": "Reviewer_S4bi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The presentation of this work is mostly clear and easy to understand.\n2. This work introduces an interesting problem when pulling one arm will affect the rewarding structure of all the other arms in the long run.\n3. Both upper bound and lower bound are presented.\n4. The experimental results are also included to highlight the efficiency of the proposed LCB method.\n\nWeaknesses:\n1. For presentation, some parts can be improved: 1. This paper uses UCB and LCB interchangeably, such as in the abstract. While I can understand that you are trying to mention the same thing when the response is reward/loss, it still feels a little bit confusing. 2. Some expression should be revised, e.g. \"not uncommon\" to \"common\" in Section 1.1.\n2. For the problem setting, especially the lower bound of the regret is in the order of T, which seems surprising. I understand your proof of Proposition 2.3. But I feel it is a little bit weird that pulling the wrong arm one time will lead to the linear regret bound in the end. Do you think it is more practical to set this correlation effect only over the next few nearby rounds?\n3. In your problem setting, the total loss does not depend on the order of actions. Can you justify this key assumption? Under that condition, repeating the horror movies for the first ten rounds and then comedies in the next ten rounds has the same effect for the further recommendation as recommending horror and comedy movie in term over the total twenty rounds. However, I think they should be drastically different in applications. I feel the correlation effect should gradually decay over time, which would be more reasonable. This is also why your lower bound is T rather than sqrt(T) as the correlation impact is currently too strong.\n4. It is better to highlight the difference between your Algorithm 1 and the traditional LCB with a couple of sentences and illustrate why it works over the traditional LCB.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a new problem of influential bandits where pulling one arm may affect the rewards of all arms in the future. To formulate this problem, this work introduces a correlation matrix and a new algorithm based on the LCB estimator tailored to the structure of the dynamic loss. This paper also gives the lower bound under this problem setting and showcases the improved regret of their proposed LCB algorithm. Some experimental results are finally presented.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weakness section above.", "broader_impact_concerns": "No ethical implications and this work is mostly theoretical.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6V0MSS3KC3", "reviewer": "Reviewer_kjw6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. It proposes an interesting bandit setting, which models the interactive influence between actions. \n\n2. It provides a complete theoretical analysis of this problem. The writing is very clear, and all the confusion caused by its difference from the traditional setting has been covered in the presentation.\n\n3. It proposes a new algorithm, which can achieve nontrivial regret guarantees on this problem, and it outperforms the classical UCB algorithm.\n\n4. The experiments are very convincing, validating the correctness of the theory.\n \nI do not find any obvious weakness", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new nonstationary bandit setting called the influential bandit, where selecting one arm may affect the reward of others, including both positive and negative influence. It models the influence with a positive semi-definite matrix, and therefore, the cumulative loss can be represented as a quadratic function. The paper proposes several theoretical results in this setting. \n\nFirst, the trivial upper bound is $O(T^2)$, which differs from traditional bandits. Second, the traditional UCB algorithm does not work well, as it will cause $\\Omega(T^2/(\\log T)^2)$ regret. Third, it constructs a hard instance to show that any early mistake can cause huge influence on the later exploration, incuring a $\\Omega(T)$ lower bound. Finally, it proposes a modified LCB algorithm that achieves $O(KT\\log T)$ regret.\n\nExperiments are conducted to validate the theoretical observation  on both synthetic\n and real-world datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the writing is pretty good, and nothing needs to be changed. But I have some questions on this topic.\n\n1. I think the current solution does not consider the effect of noise. In the classical UCB algorithm, the UCB term $\\sqrt{\\log t/n_i}$ is incorporated to address the randomness of noise. However, in the influential LCB algorithm, the estimated loss is directly chosen to be that at the current step, without using the information from previous rounds, and no similar $\\sqrt{\\log t/n_i}$ term due to the noise. Is my understanding correct? \n\n2. Other than UCB, another classical algorithm for bandits is Thompson sampling (TS). How do you think TS will behave in this setting?\n\n3. In classical bandits, a lower bound dependent on the number of actions $K$ can be proved. Is it also possible in the influential bandit setting?\n\nI think it would be better if these questions could be further discussed. But if not, the paper is still very good.", "broader_impact_concerns": "This work introduces an interesting setting for handling the influence of past actions in the decision-making under uncertainty problem. It may be interesting to other researchers working on bandits and reinforcement learning.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4MZSClE1p3", "reviewer": "Reviewer_hdkq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. To the best of my knowledge, this is the first paper to consider a setting where the loss of an arm is influenced by the prior selections of all arms. The motivation for this problem is clear and intuitive.\n\n2. The authors establish regret lower bounds for this new problem setting.\n\n3. The authors propose Influential LCB, a simple yet effective algorithm for this new problem, and provide a thorough theoretical analysis of its regret.\n \n4. The effectiveness of the proposed algorithm and the influential bandit model is empirically validated through experiments, which support the theoretical regret bounds and highlight the significance of the new framework.\n \n5. The discussion section thoroughly addresses the limitations and assumptions of the model, demonstrating strong awareness of potential weaknesses.\n\n\n**Weaknesses**\n\n1. Model Assumption: The authors assume a symmetric, positive semi-definite interaction matrix to capture the dynamics of arm losses. While they clearly discuss the limitations of the positive semi-definite assumption in the discussion section, I am curious about the necessity of the *symmetric* condition. For example, watching a movie trailer may reduce the loss of the full movie, but watching the full movie might increase the loss (i.e., reduce interest) in the trailer since the user has already seen the content. I wonder how the model performs without the symmetry constraint—specifically, what happens to the MSE in Section 4.2 when the interaction matrix is not assumed to be symmetric?\n\n2. Loss Update Rule: The expected loss of each arm is updated by simply adding the effect from the selected arm via the interaction matrix. However, it may be more realistic to discount the effects of older interactions and place greater weight on more recent ones. For instance, consider watching in the order: movie 1, movie 1, movie 2, ..., movie 100 versus movie 1, movie 2, ..., movie 100, movie 1. According to the model, the final loss would be the same, which seems counterintuitive. Proposition 2.1 is elegant, but the claim that the total loss does not depend on the order of actions feels unrealistic.\n\n3. Readability of the Proof: While I verified the correctness of the proofs, the paper would benefit from sketches or summaries of key proof ideas to improve readability. For example, $x^*$  minimizes the total loss $\\mathcal{L}$, while $p^*$ minimizes the quadratic term $\\mathcal{L}_2$. The proof converts $x^*$ to $p^*$ to establish an upper bound, but I wonder whether this introduces a gap in tightness. \nIs the use of $p^*$ essential for the regret bound? I would be curious to hear the intuition behind introducing $p^*$, which minimizes $\\mathcal{L}_2$, instead of directly reasoning about the true minimizer of $\\mathcal{L}$.\n\n4. Reference to Frank-Wolfe Algorithm: Since the analysis draws parallels with the Frank-Wolfe algorithm, especially in the convergence behavior, it would be helpful to include references to relevant works on Frank-Wolfe, particularly those covering its convergence analysis.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the influential bandit problem, a novel extension of the classical multi-armed bandit framework where selecting one arm can influence the future losses of other arms. The authors begin by analyzing the theoretical properties of this setting, showing that the standard LCB algorithm suffers from a near-quadratic regret lower bound. They also prove the existence of instances where any algorithm must incur at least $\\Omega(T)$ regret.\n\nTo address this challenge, the authors propose a simple yet effective algorithm, Influential LCB, and show that it achieves near-optimal regret of $O(KT \\log T)$ under mild assumptions. They support this result with regret analysis on synthetic datasets. Furthermore, through model analysis on a real-world dataset, they demonstrate that the influential bandit assumption better captures the observed dynamics than the traditional stationary loss assumption.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the weaknesses mentioned in the **Strengths and Weaknesses** section.\n\nAdditionally, in Section 4.1, I would be interested to see the regret analysis results when the number of arms is larger (e.g., K = 10).\n\n\nMinor Changes:\n- In Proposition 2.1, clearly define the vector $l^{(1)}$.\n- On page 3, make sure matrix $A$ is consistently written in bold. ($A_{horror, horror}, A_{comedy, horror}$)\n- On page 5, above equation (13), define $\\mathbb{Z}_{*}^K$.\n- On page 6, in equation (22), replace $L_2$ with $\\mathcal{L}_2$.\n- In equations (39) and (40), $g \\rightarrow gᵀ$?\n- In equation (61), $(2+ 2 ||l^{(1)}||_\\infty + 4) \\log T \\rightarrow (2K+2|| l^{(1)}|| + 4) \\log T$  ?\n- On page 10, $L^* \\rightarrow \\mathcal{L}^*$", "broader_impact_concerns": "As this work is theoretical and centers on a new algorithm for sequential decision-making, there are no apparent ethical concerns arising directly from its content.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)