Online learning with Erdős–Rényi side-observation graphs
arXiv:2604.25271v1 [stat.ML] 28 Apr 2026
Tomáš Kocák SequeL team INRIA Lille - Nord Europe
Gergely Neu Universitat Pompeu Fabra Barcelona, Spain
Abstract We consider adversarial multi-armed bandit problems where the learner is allowed to observe losses of a number of arms beside the arm that it actually chose. We study the case where all non-chosen arms reveal their loss with an unknown probability rt , independently of each other and the action of the learner. Moreover, we allow rt to change in every round t, which rules out the possibility of estimating rt by a well-concentrated sample average. We propose an algorithm which operates under the assumption that rt is large enough to warrant at least one side observation with high probability. We show that after T rounds in a bandit problem with N arms, the expected regret of our algorithm is qP T (1/r ) log N , given that of order O t t=1 rt ≥ log T /(2N − 2) for all t. All our bounds are within logarithmic factors of the best achievable performance of any algorithm that is even allowed to know exact values of rt .
1
INTRODUCTION
In sequential learning, a learner is repeatedly asked to choose an action for which it obtains a loss and receives a feedback from the environment (Cesa-Bianchi and Lugosi, 2006). We typically study two feedback settings: the learner either observes the losses for all the potential actions (full information) or it observes only the loss of the action it chose. This latter feedback scheme is known as the bandit setting (cf. Auer et al., 2002a). In this paper, instead of considering these two limit cases, we study a more refined feedback model, known as bandit with side observations (Mannor and Shamir, 2011; Alon et al., 2013; Kocák et al., 2014, 2016), that generalizes both of them. Typical examples for learning with full information and bandit feedback are sequential trading on a stock market
Michal Valko SequeL team INRIA Lille - Nord Europe
(where all stock prices are fully observable after each trading period), and electronic advertising (where the learner can only observe the clicks on actually shown ads), respectively. However, advertising in a social network offers a more intricate user feedback than captured by the basic bandit model: when proposing an item to a user in a social network, the advertiser can often learn about the preferences of the user’s connections as well. Naturally, the advertiser would want to improve its recommendation strategy by incorporating these side observations. Besides advertising and recommender systems, side observations can also arise in sensor networks, where the action of the learner amounts to probing a particular sensor. In this setting, each sensor can reveal readings of some other sensors that are in its range. When our goal is to sequentially select a sensor maximizing a property of interest, a good learning strategy should be able to leverage these side readings. In this paper, we follow the formalism of Mannor and Shamir (2011) who model side observations with a graph structure over the actions: two actions mutually reveal their losses if they are connected by an edge in the graph in question. In a realistic scenario this graph is time dependent and unknown to the learner (e.g., the advertiser or the algorithm scheduling sensor readings). All previous algorithms for the studied setting (Mannor and Shamir, 2011; Alon et al., 2013; Kocák et al., 2014, 2016) require the environment to reveal a substantial part of a graph, at least after the side observations have been revealed. Specifically, these algorithms require the knowledge of the second neighborhood (the set of neighbors of the neighbors) of the chosen action in order to update their internal loss estimates. On the other hand, they are able to handle arbitrary graph structures, potentially chosen by an adversary and prove performance guarantees using graph properties based on cliques or independence sets. The main contribution of our work is a learning algorithm that, unlike previous solutions, does not require the knowledge of the exact graph underlying the observations, beyond knowing from which nodes the side observations
came from. Relaxing this assumption, however, has to come with a price: As the very recent results of Cohen et al. (2016) show, achieving nontrivial advantages from side observations may be impossible without perfectly known side-observation graphs when an adversary is allowed to pick both the losses and the side-observation graphs. On the positive side, Cohen et al. offer efficient algorithms achieving strong improvements over the standard regret guarantees under the assumption that the losses are generated in an i.i.d. fashion and the graphs may be generated adversarially. Complementing these results, we consider the case of adversarial losses and make the assumption that the side-observation graph in round t is generated from an Erdős–Rényi model with an unknown and time-dependent parameter rt . The main challenge for the learner is then the necessity to exploit the side observations despite not knowing the sequence (rt ). It is easy to see that this model can be equivalently understood as each non-chosen arm revealing its loss with probability rt , independently of all other observations. That said, we still find it useful to think of the side observations as being generated from an Erdős–Rényi model, as it allows direct comparisons with the related literature. In particular, the case of learning with Erdős–Rényi side-observation graphs was considered before by Alon et al. (2013): Given full access to the underlying graph structure, their algorithm Exp3-SET can be shown to guarantee pP a regret bound N of O t (1/rt )(1 − (1 − rt ) ) log N . While the assumption of having full access to the graph can be dropped relatively easily in this particular case, exact knowledge of rt seems to be crucial for constructing reliable loss estimates and use them to guide the choice of action in each round. It turns out that the problem of estimating rt while striving to perform efficiently is in fact a major difficulty in our setting. Indeed, as we allow rt to change arbitrarily between each round, we cannot rely on any past observations to construct well-concentrated estimates of these parameters. That is, the main challenge is estimating rt from only a handful of samples. The core technical tool underlying our approach is a direct estimation procedure for the losses that does not estimate rt explicitly. Armed with this estimation procedure, we propose a learningp algorithm called Exp3-Res that guarantees a regret of P O( (1/r t ) log N ), provided that rt ≥ log T /(2N −2) t holds for all rounds t. This assumption essentially corresponds to requiring that, with high probability, at least 1 side observation is produced in every round, or, in other words, the side-observation graphs encountered are all nonempty. Notice that for the assumed range of rt ’s, our regret bound improves √ upon the standard regret bound of Exp3, which is of O( N T log N ). It is easy to see that when rt becomes smaller than 1/N , side observations become unreliable and the bound of Exp3 cannot be improved. That
is, if our assumption cannot be verified a priori, then ignoring all side observations and using the Exp3 algorithm of Auer et al. (2002a) instead can yield a better performance. On the other hand, given that our assumption holds, our bounds cannot be significantly improved as suggested by p the lower-bound of Ω( T /r) proved for a static r by Alon et al. 2013. Many other partial-information settings have been studied in previous work. One of the simplest of these settings is the label-efficient prediction game considered by CesaBianchi et al. (2005), where the learner can observe either losses of all the actions or none of them, not even the loss of the chosen action. This observation can be queried by the learner at most an ε < 1 fraction of the total number of rounds, which means no losses are observed in the remaining rounds. An even more restricted information setting, label efficient bandit feedback was considered by Allenberg et al. (2006), where the learner can only query the loss of the chosen action, instead of all losses (see also Audibert and Bubeck,p 2010). Algorithms p for these two settings have e N T /ε), respectively. While e T /ε) and O( regret of O( these bounds may appear very similar to ours, notice that our setting offers a more intricate (and, for some problems, more realistic) feedback scheme, which also turns out to be much more challenging to exploit. In another related setting, Seldin et al. (2014) consider M side observations that the learner can proactively choose in each round without limitations. Seldin et al. deliver an algorithm with regret p e (N/M )T ), also proving that choosing M observaof O( tions uniformly at random is minimax optimal; given this sampling scheme, it is not even necessary to observe the loss of the chosen action. Their result is comparable to ours and the result by Alon et al. (2013) for Erdős–Rényi observation graphs with parameter r = M/N . However, Seldin et al. also assume that M is known, which obviates the need for estimating r. We provide a more technical discussion on the related work in Section 6. In our paper, we assume that, just like the observation probabilities, the losses are adversarial, that is, they can change at each time step without restrictions. Learning with side observations and stochastic losses was studied by Caron et al. (2012) and Buccapatnam et al. (2014). While this is an easier setting that the adversarial one, the authors assumed, in both cases, that the graphs have to be known in advance. Recently, Carpentier and Valko (2016) studied another stochastic setting where the graph is also not known in advance, however their setting considers different feedback and loss structure (influence maximization) which differs from the side-observation setting. Furthermore, Alon et al. (2015) considered a strictly more difficult setting than ours, where the loss of the chosen action may not be a part of the received feedback.
2
PROBLEM DEFINITION
We now formalize our learning problem. We consider a sequential interaction scheme between a learner and an environment, where the following steps are repeated in every round t = 1, 2, . . . , T : 1. The environment chooses rt ∈ [0, 1] and a loss function over the arms, with ℓt,i being the loss associated def
with arm i ∈ [N ] = {1, 2, . . . , N } at time t. 2. Based on its previous observations (and possibly some randomness), the learner draws an arm It ∈ [N ]. 3. The learner suffers loss ℓt,It . 4. For all i ̸= It , Ot,i is independently drawn from a Bernoulli distribution with mean rt . Furthermore, Ot,It is set as 1. 5. For all i ∈ [N ] such that Ot,i = 1, the learner observes the loss ℓt,i . The goal of the learner is to minimize its total expected losses, or, equivalently, to minimize the total expected regret (or, in short, regret) defined as " T # X RT = max E (ℓt,It − ℓt,i ) . i∈[N ]
t=1
We will denote the interaction history between the learner and the environment up to the beginning of round t by Ft−1 . We also define pt,i = P [ It = i| Ft−1 ]. The main challenge in our setting is leveraging side observations without knowing rt . Had we had access to the exact value of rt , we would be able to define the following estimate of ℓt,i : ℓb⋆t,i =
Ot,i ℓt,i pt,i + (1 − pt,i )rt
(1)
It is easy to see that the loss estimates defined h i this way b are unbiased in the sense that E ℓt,i Ft−1 = ℓt,i for all t and i. It is also straightforward to show that an appropriately tuned instance of the Exp3 algorithm of Auer et al. (2002a) fed with p these P loss estimates is guaranteed to achieve a regret of O( t (1/rt ) log N ) (see also Seldin et al. 2014). Then, one might consider a simple algorithm that devotes a number of observations to obtain an estimate rbt of rt and plug this estimate into (1). However, notice that since rt is allowed to change arbitrarily over time, we can only work with a severely limited sample budget for estimating rt : only N − 1 independent observations! Thus, we can obtain only very loose confidence intervals around rt which translate to even more useless confidence intervals around ℓb⋆t,i .
Below, we describe a simple trick for obtaining loss estimates that have similar properties to the ones defined in (1) without requiring exact knowledge or even explicit estimation of rt . Our procedure is based on the geometric resampling method of Neu and Bartók (2013). To get an intuition of the method, let us assume that we have access to the independent geometrically distributed random variable G⋆t,i with parameter ot,i = pt,i + (1 − pt,i )rt . Then, replacing 1/ot,i by G⋆t,i in the definition of ℓb⋆t and ensuring that G⋆t,i is independent of Ot,i , we can obtain an unbiased loss estimate essentially equivalent to ℓb⋆t . The challenge posed by this approach is that in our setting, we do not have exact sample access to the geometric random variable G⋆t,i . In the next section, we describe our algorithm that is based on replacing G⋆t,i in the above definition by an appropriate surrogate.
3
ALGORITHM
Our algorithm is called Exp3-Res and displayed as Algorithm 1. It is based on the Exp3 algorithm of Auer et al. (2002a) and crucially relies on the construction of a surrogate Gt,i of G⋆t,i . Throughout this section, we will assume log T of havthat rt ≥ 2N −2 , which implies that the probability √ ing no side observations in round t is of order 1/ T . The algorithm is initialized by setting w1,i = 1/N for all i ∈ [N ], and then performing the updates wt+1,i =
1 b t,i exp −ηt+1 L N
(2)
after each round t, where ηt+1 > 0 is a parameter of the b t,i is cualgorithm called the learning rate in round t and L mulative sum of the loss estimates ℓbs,i up to (and including) time t. In round t, the learner draws its action It such that It = i holds with probability pt,i ∝ wt,i . To simplify some of the notation below, we introduce the shorthand notations Pt [·] = P [ ·| Ft−1 ] and Et [·] = E [ ·| Ft−1 ]. For any fixed t, i, we now describe an efficiently computable surrogate Gt,i for the geometrically distributed random variable G⋆t,i with parameter ot,i that will be used for constructing our loss estimates. In particular, our strategy ′ will be to construct several independent copies Ot,i (k) of Ot,i and choosing Gt,i as the index k of the first copy ′ with Ot,i (k) = 1. It is easy to see that with infinitely many copies, we could exactly recover G⋆t,i ; our actual surrogate is going to be weaker thanks to the smaller sample size. For clarity of notation, we will omit most explicit references to t and i, with the understanding that all calculations need to be independently executed for all pairs t, i. Let us now describe our mechanism for constructing the copies {O′ (k)}. Since we need independence of Gt,i and Ot,i for our estimates, we use only side observations from
actions [N ] \ {It , i}. First, let’s define σ as a uniform random permutation of [N ] \ {It , i}. For all k ∈ [N − 2], we define R(k) = Ot,σ(k) . Note that due to the construc−2 tion, {R(k)}N k=1 are pairwise independent Bernoulli random variables with parameter rt , independent of Ot,i . Furthermore, knowing pt,i we can define P (1), . . . , P (N −2) as pairwise independent Bernoulli random variables with parameter pt,i . Using P (k) and R(k) we define the random variable O′ (k) as
Algorithm 1 Exp3-Res 1: Input: 2: Set of actions [N ]. 3: Initialization: b 0,i ← 0 for i ∈ [N ]. 4: L 5: Run: 6: for t = 1r to T do 7:
ηt ←
log N
. Pt−1 PN N 2 + s=1 i=1 ps,i (ℓbs,i )2 .
b t−1,i ) for i ∈ [N ]. wt,i ← (1/N ) exp(−ηt L PN 9: Wt ← i=1 wt,i . 10: pt,i ← wt,i /Wt . 11: Choose It ∼ pt = (pt,1 , . . . , pt,N ). 12: Receive the observation set Ot . 13: Receive the pairs {i, ℓt,i } for all i s.t. Ot,i = 1. 14: Compute Gt,i for all i ∈ [N ] using (3). 15: ℓbt,i ← ℓt,i Ot,i Gt,i for all i ∈ [N ]. b t,i = L b t−1,i + ℓbt,i for all i ∈ [N ]. 16: L 17: end for 8:
O′ (k) = P (k) + (1 − P (k))R(k) for all k ∈ [N − 2]. Using independence of all previously defined random variables, it is easy to check that the vari−2 ables {O′ (k)}N k=1 are pairwise independent Bernoulli random variables with expectation ot,i = pt,i + (1 − pt,i )rt . Now we are ready to define Gt,i as Gt,i = min {k ∈ [N − 2] : O(k)′ = 1} ∪ {N − 1} . (3) The following lemma states some properties of Gt,i . Lemma 1. For any value of g we have 1 1 − (1 − ot,i )N −1 ot,i ot,i 2 − ot,i 1 + 2 (1 − ot,i )N −2 × E G2t,i = o2t,i ot,i × o2t,i + ot,i − 2 + 2ot,i (N − 2)(ot,i − 1) E [Gt,i ] =
Proof. The proof follows directly from using the definition of Gt,i and simplifying the sums E [Gt,i ] =
N −2 X
log T Lemma 2. Assume rt ≥ 2N −2 . Then, for all t and i,
h i 1 0 ≤ ℓt,i − Et ℓbt,i ≤ √ . T Proof. Fix an arbitrary t and i. Using Lemma 1 along with Et [Ot,i ] = ot,i and the independence of Gt,i and Ot,i , we get
kot,i (1 − ot,i )k−1 +
k=1
+ (N − 1) (1 − ot,i )N −2 , −2 NX 2 k ot,i (1 − ot,i )k−1 + E G2t,i =
h i Et ℓbt,i = Et [Gt,i Ot,i ℓt,i ] = ℓt,i − ℓt,i (1 − ot,i )N −1 ,
k=1
which h iimmediately implies the lower bound on ℓt,i − Et ℓbt,i . For proving the upper bound, observe that
2
+ (N − 1) (1 − ot,i )N −2 .
Using Lemma 1, it is easy to see that Gt,i follows a truncated geometric law in the sense that P [Gt,i = m] = P min G⋆t,i , N − 1 = m holds for all m ∈ [N − 1]. Using all this notation, we construct an estimate of ℓt,i as ℓbt,i = Gt,i Ot,i ℓt,i .
Ot,i is also independent of Ot,j for j ̸∈ {i, It }. As a result, Gt,i is independent of Ot,i , and we can use the identity Et [Gt,i Ot,i ] = Et [Gt,i ] Et [Ot,i ]. The next lemma relates the loss estimates (4) to the true losses, relying on the oblog T servations above and the assumption rt ≥ 2N −2 .
(4)
The rationale underlying this definition of Gt,i is rather delicate. First, note that pt,i is deterministic given the history Ft−1 and therefore, does not depend on Ot,i . Second,
1 ℓt,i (1 − ot,i )N −1 ≤ (1 − rt )N −1 ≤ e−rt (N −1) ≤ √ T holds by our assumption on rt , where we used the elementary inequality 1 − x ≤ e−x that holds for all x ∈ R. The next theorem states our main result concerning Exp3-Res with an adaptive learning rate. log T Theorem 1. Assume that rt ≥ 2N −2 holds for all t and set s log N ηt = . Pt−1 PN 2 N + ps,i (ℓbs,i )2 s=1
i=1
which, together with the last inequality, gives us
Then, the expected regret of Exp3-Res satisfies v ! u T u X √ 1 log N + T . RT ≤ 2t N 2 + r t=1 t
4
N X
N 2 log W ηt X log Wt+1 t pt,i ℓbt,i ≤ pt,i ℓbt,i + − 2 i=1 ηt ηt+1 i=1
for every t ∈ [T ]. Taking expectations and summing over time, we get
PROOF OF THEOREM 1
In this section, we present details of the proof of Theorem 1 but first, we state an auxiliary lemma. Lemma 3 (Lemma 3.5 of Auer et al., 2002b). Let b1 , b2 , . . . , bT be non-negative real numbers. Then T X t=1
b qP t
t s=1 bs
q PT ≤2 t=1 bt .
Proof. The proof is based on the inequality x/2 ≤ 1 − √ Pt 1 − x for x ≤ 1. Setting x = bt /q s=1 bs and multiplyPt ing both sides of the inequality by s=1 bs we get b qP t
≤
q
t s=1 bt
Pt
s=1 bs −
q
E
=
N X 1 b log pt,i e−ηt ℓt,i ηt i=1
≤
N X 1 log pt,i 1 − ηt ℓbt,i + (ηt ℓbt,i )2 ηt i=1
(5)
N N X X 1 = log 1 − ηt pt,i ℓbt,i + ηt2 pt,i (ℓbt,i )2 ηt i=1 i=1
!
i=1
≤
N
e
N X 1 i=1
N
=
i=1
! e
b t,i −ηt L
ηt+1 ηt
N
e
t=1 i=1
Note that this is the only step in the analysis where the actual magnitude (and not just the sign) of the √ bias of the loss estimates shows up. Anything bigger than T would degrade our final regret bound. We are left with bounding the two terms on the right-hand side. To simplify some notation below, let us define bt = PN b 2 i=1 pt,i (ℓt,i ) . By our definition of ηt and the help of Lemma 3, we can bound the first term on the right hand side as # " T √ T X X ηt bt b log N q t = E E Pt−1 2 t=1 2 N 2 + t=1 b s=1 s # "r PT 2 N + t=1 bt log N ≤E ≤
Using ηt+1 ≤ ηt and Jensen’s inequality, we get b t,i −ηt L
# T X N X √ b pt,i ℓt,i ≥ pt,i ℓt,i + T .
,
where in (5), we used the inequality exp(−x) ≤ 1 − x + x2 that holds for x ≥ −1. Further, we used the inequality log(1 − x) ≤ −x, which holds for all x ≤ 1, to upper bound the last term.
N X 1
" T N XX t=1 i=1
b t−1,i −ηt ℓbt,i N 1 −ηt L X e W′ 1 1 Ne log t+1 = log ηt Wt ηt W t i=1
Wt+1 =
The goal of the second part of the analysis is to construct bounds for each of the three expectations in the previous inequality. For the term on the left-hand side, we use Lemma 2 to get the lower-bound
s=1 bs − bt .
The first part of the analysis follows the proof of Lemma 1 by Györfi and Ottucsák (2007). Defining Wt′ = P b N 1 −ηt−1 Lt−1,i , we get i=1 e N
b t,i −ηt+1 L
# # " T N 2 X ηt X b b E pt,i ℓt,i pt,i ℓt,i ≤ E 2 i=1 t=1 i=1 t=1 " T # X log Wt log Wt+1 . − +E ηt ηt+1 t=1
Pt
The proof is concluded by summing over t.
N X 1
" T N XX
t
N2 +
E [b ] log N , t t=1
PT
where we also used the fact that N 2 ≥ bt and Jensen’s inequality in the last line. We continue by bounding E [bt ]:
Et ηt+1 η
r
"N X i=1
# N X 2 b pt,i (ℓt,i ) = pt,i ℓ2t,i Et Ot,i G2t,i i=1 N X
(6)
2 − ot,i 2 ≤ pt,i ot,i ≤ , 2 ot,i rt i=1
ηt+1
′ = (Wt+1 ) ηt ,
where we used ot,i ≥ rt together with the second part of Lemma 1 which gives us
2 − ot,i 1 + 2 (1 − ot,i )N −2 × Et G2t,i = o2t,i ot,i × o2t,i + ot,i − 2 + 2ot,i (N − 2)(o − 1) ≤
2 − ot,i , o2t,i
since both o2t,i + ot,i − 2 and 2ot,i (N − 2)(o − 1) are nonpositive. Thus, we obtain " T # v ! u T u X 1 X ηt bt t E ≤ (7) + N 2 log N . 2 r t=1 t=1 t Finally, using W1 = 1, the sum in the last expectation telescopes to " T # X log Wt log Wt+1 log WT +1 E − =E − . ηt ηt+1 ηT +1 t=1 Using the definition of Wt , we get that log WT +1 log wT +1,j E − ≤E − ηT +1 ηT +1 h i log N b T,j ≤E +E L ηT +1 holds for any arm j ∈ [N ]. Now note that the first term can be bounded by using the definition of ηTh+1 with the help i b of (6) and Jensen’s inequality. Using Et ℓt,i ≤ ℓt,i from Lemma 2 and combining everything together, we obtain the regret bound " T # " # X X RT = E pt,i ℓt,i − min E ℓt,j t=1
j∈[N ]
t∈Tk
v ! u T u X √ 1 t 2 N + log N + T . ≤2 r t=1 t
5
EXPERIMENTS
In this section, we study the empirical performance of Exp3-Res compared to three other algorithms: • Exp3 – a basic adversarial multi-armed bandit algorithm which uses only loss observations of chosen arms and discards all side observations. • Oracle – full-information algorithm with access to losses of every action in every time step, regardless of the value of rt . Our particular choice is Hedge (Littlestone and Warmuth, 1994; Freund and Schapire, 1997).
• Exp3-R – a variant of the Exp3-Res algorithm with access to the sequence (rt )Tt , using (1) to construct unbiased loss estimate instead of using geometric resampling. The most interesting parameter of our experiment is the sequence (rt ), since it controls amount of side observation presented to the learner. In order to show that Exp3-Res can effectively make use of the additional information provided by the environment, we designed several sequences (rt ) with different amounts of side observation provided to the learner. In the case of small rt -s, the problem is almost as difficult as the multi-armed bandit problem. On the other hand, in the case of large rt -s, the problem is almost as easy as the full-information problem. Therefore, we expect that the performance of Exp3-Res will interpolate between the performance of the Exp3-R and Oracle algorithms depending on the values of the rt -s. In the next section, we validate this claim empirically. 5.1
EXPERIMENT DETAILS
To ensure sufficient challenge for the algorithms, we have generated a sequence of losses as a random walk for each arm with independent increments uniformly distributed on [−0.1, 0.1] while enforcing the random walks to stay within [0, 1] by setting the value of a random walk to 0 or 1, respectively, if the random walk gets outside the boundaries. The loss sequence is fixed through all of the experiments to demonstrate the impact of the sequence (rt )Tt on the regret of algorithms. We have observed qualitatively similar behavior for other loss sequences. We fix the number of arms in all of the experiments as 50, and the time horizon as 500. Every curve represents an average of 100 runs. 5.2
RESULT OF THE EXPERIMENTS
We performed experiments on many different loss sequences and sequences of rt -s. Since the results are essentially the same for all the different sequences, we included in the present paper just the results for one loss sequence with different sequences of rt -s. In the case of rt ≥ log(T )/(2N − 2), the case of high probability of having some side observation, the performance of the algorithm Exp3-Res proposed in the present paper is comparable to the performance of the idealistic Exp3-R which knows exact value of rt in every time step. Moreover, if the average rt is close to 1, the performance of the proposed algorithm is close to the performance of Oracle which observes all the losses. If the average rt is close to zero, the performance of the algorithm is a little bit worse than the performance of basic Exp3. This is also supported by the theory, since our algorithm is not able to construct reliable estimates in the case of small rt -s.
100
80 60 40
100
200 300 Time
400
100
200 300 Time
400
20
0 0
500
100
60 40
80
0 0
0 0
400
300
400
500
500
120
40 20
200 300 Time
200
140 Exp3−Res Oracle (Hedge) Exp3 Exp3−R
60
20 100
100
Time
120 Exp3−Res Oracle (Hedge) Exp3 Exp3−R
Cumulative regret
Cumulative regret
40
(b) Static sequence (rt )Tt , rt = 0.06 ≈ (c) Changing sequence (rt )Tt with unilog(T )/(2N − 2) formly distributed rt on [0, 0.2]
120
80
40
0 0
500
(a) Static sequence (rt )Tt , rt = 0
100
60
60
Exp3−Res Oracle (Hedge) Exp3 Exp3−R
20
20 0 0
80
80 Exp3−Res Oracle (Hedge) Exp3 Exp3−R
Total regret
100
120 Exp3−Res Oracle (Hedge) Exp3 Exp3−R
Cumulative regret
Cumulative regret
120
Cumulative regret
140
100 80 60 Exp3−Res Oracle (Hedge) Exp3 Exp3−R
40 20 100
200 300 Time
400
500
0 0
0.2
0.4 0.6 Fixed value of r
0.8
1
(d) Sequence (rt )Tt generated as a random (e) Sequence (rt )Tt generated as a random (f) Total regret for different values of static (rt )Tt walk on [0, 0.1] walk on [0, 1]
Figure 1: Comparison of algorithms for different amount of side information sequences (different sequences (rt )Tt )
6
CONCLUSION & FUTURE WORK
In this paper, we considered multi-armed bandit problems with stochastic side observations modeled by Erdős– Rényi graphs. Our contribution is a computationally efficient algorithm that operates under the assumption rt ≥ log T /(2N − 2), which essentially guarantees that at least one piece of side observation is generated in every round, with high probability. In this case, our algorithm q guarPT 1 antees a regret bound of O log N t=1 rt (Theorem 1). In this section, we discuss several open questions regarding this result. The most obvious question is whether it is possible to remove our assumptions on the values of rt . We can only give a definite answer in the simple case when all rt ’s are identical: In this case, one can think of simply computing the empirical frequency rbt of all previous side observations in round t to estimate the constant r, plug the result into (1), and then use the resulting loss estimates in an exponentialweighting scheme. It is relatively straightforward (but also rather tedious) to show that the p resulting algorithm satisfies e a regret bound of O T /r for all possible values of r, thanks to the fact that r̂t quickly concentrates around the
true value of r. Notice however that this approach clearly breaks down if the rt ’s change over time. In the case of changing rt ’s, the number of observations we can use to estimate rt is severely limited, so much that we cannot expect any direct estimate of rt to concentrate around the true value. Our algorithm proposed in Section 3 gets around this problem by directly estimating the importance weights 1/ot,i instead of rt , which enables us to construct reliable loss estimates, although only at the price of our assumption on the range of rt . While we acknowledge that this assumption can be difficult to confirm a priori in practice, we remark that we find it quite surprising that any algorithm whatsoever can take advantage of such limited observations, even under such a restriction. We also point out that for values of rt that are consistently below our bound, it is not possible to substantially √ improve the regret e bounds of Exp3 which are of O T N , as shown by the lower bounds of Alon et al. (2013). We expect that in several practical applications, one can verify whether the rt ’s satisfy our assumption or not, and decide to use Exp3-Res or Exp3 accordingly. In fact, our experiments suggest that our algorithm performs well even if neither of these two assumptions are verified: we have seen that the empirical performance of Exp3-Res is only slightly worse than that
of Exp3 even when the values of rt are very small (Section 5). Still, finding out whether our restriction on rt can be relaxed in general is a very important and interesting question left for future study. An important corollary of our results is that, under some assumptions, it is possible to leverage side observations in a non-trivial way without having access to the second neighborhoods in the side-observation graphs as defined by Mannor and Shamir (2011). This complements the recent results of Cohen et al. (2016), who show that non-stochastic side-observations may provide non-trivial advantage over bandit feedback when the losses are stochastic even when the side-observation graphs are unobserved, but learning with unobserved feedback graphs can be as hard as learning with bandit feedback when both the losses and the graphs are generated by an adversary. A natural question that our work leads to is whether it is possible to efficiently leverage side-observations under significantly weaker assumptions on the observation model. Acknowledgements The research presented in this paper was supported by CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020, French Ministry of Higher Education and Research, NordPas-de-Calais Regional Council, French National Research Agency project ExTra-Learn (n.ANR-14-CE24-0010-01), and by UPFellows Fellowship (Marie Curie COFUND program n◦ 600387).
References Allenberg, C., Auer, P., Györfi, L., and Ottucsák, Gy. (2006). Hannan consistency in on-line learning in case of unbounded losses under partial monitoring. In Algorithmic Learning Theory (ALT), pages 229–243. Alon, N., Cesa-Bianchi, N., Dekel, O., and Koren, T. (2015). Online learning with feedback graphs: Beyond bandits. In Conference on Learning Theory (COLT). Alon, N., Cesa-Bianchi, N., Gentile, C., and Mansour, Y. (2013). From bandits to experts: A tale of domination and independence. In Neural Information Processing Systems (NeurIPS).
In International Conference on Measurement and Modeling of Computer Systems. Caron, S., Kveton, B., Lelarge, M., and Bhagat, S. (2012). Leveraging side observations in stochastic bandits. In Conference on Uncertainty in Artificial Intelligence (UAI). Carpentier, A. and Valko, M. (2016). Revealing graph bandits for maximizing local influence. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 10–18. Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge University Press, New York, NY. Cesa-Bianchi, N., Lugosi, G., and Stoltz, G. (2005). Minimizing regret with label efficient prediction. IEEE Transactions on Information Theory, 51(6):2152–2162. Cohen, A., Hazan, T., and Koren, T. (2016). Online learning with feedback graphs without the graphs. In International Conference on Machine Learning (ICML). Freund, Y. and Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55:119–139. Györfi, L. and Ottucsák, Gy. (2007). Sequential prediction of unbounded stationary time series. IEEE Transactions on Information Theory, 53(5):1866–1872. Kocák, T., Neu, G., and Valko, M. (2016). Online learning with noisy side observations. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1186–1194. Kocák, T., Neu, G., Valko, M., and Munos, R. (2014). Efficient learning by implicit exploration in bandit problems with side observations. In Neural Information Processing Systems (NeurIPS), pages 613–621. Littlestone, N. and Warmuth, M. (1994). The weighted majority algorithm. Information and Computation, 108(2):212–261. Mannor, S. and Shamir, O. (2011). From bandits to experts: On the value of side-observations. In Neural Information Processing Systems (NeurIPS).
Audibert, J.-Y. and Bubeck, S. (2010). Regret bounds and minimax policies under partial monitoring. Journal of Machine Learning Research, 11:2785–2836.
Neu, G. and Bartók, G. (2013). An efficient algorithm for learning with semi-bandit feedback. In Algorithmic Learning Theory (ALT).
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002a). The non-stochastic multi-armed bandit problem. SIAM Journal on Computing, 32(1):48–77.
Seldin, Y., Bartlett, P., Crammer, K., and Abbasi-Yadkori, Y. (2014). Prediction with limited advice and multiarmed bandits with paid observations. In International Conference on Machine Learning (ICML).
Auer, P., Cesa-Bianchi, N., and Gentile, C. (2002b). Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64:48–75. Buccapatnam, S., Eryilmaz, A., and Shroff, N. B. (2014). Stochastic bandits with side observations on networks.