Bandits with Concave Aggregated Reward

1 Introduction

Multi-Armed Bandit (MAB) is one of the most classical frameworks for making decisions sequentially under uncertainty. In this setting, an agent chooses an action and receives a reward in each round. The agent aims to maximize her/his cumulative reward during the game by capturing the exploration-exploitation tradeoff. Based on the basic bandits model, many studies have proposed a number of variants, and a large number of algorithms have emerged to tackle related problems [Gittins, 1979; Agrawal et al., 1988; Auer et al., 2002a; Maillard et al., 2011; Li et al., 2023]. These bandit models have been applied across various domains, such as advertisements [Li et al., 2010; Li et al., 2011], dynamic procurement [Badanidiyuru et al., 2012; Badanidiyuru et al., 2013] and crowdsourcing platforms [Slivkins and Vaughan, 2014].

The classical bandit problems often assume that the pulls of arms are independent and the cumulative reward of the pulled arms is a linear function of all actions over the time horizons T. However, due to the diminishing marginal utility, in many application domains, the agent collects a concave aggregated reward: 1) the marginal utility of each arm gradually decreases, 2) the value generated by a selected arm in each round will impact the subsequent rounds' rewards. For example, an advertiser wants to promote a new product. There are several different advertisements to choose from, and different advertisements have different effects on the product's popularity. The advertiser has to decide which advertisement to use on each day. In this scenario, each arm corresponds to an advertisement, and the total reward corresponds to the product's popularity or the number of registered users. Since the decay of Click-Through-Rate(CTR) is largely due to the amount of repeat exposure[Agarwal et al., 2009], the longer the advertising time, the more people learn about the product, and the diminishing marginal utility leads to a decline in the growth rate of the product's popularity. The advertiser aims to the expose product to more people, i.e., to maximize the aggregated reward over the total T rounds. In this problem, due to diminishing marginal rewards, even if the increase in product popularity on the first day is more significant than that on the second day, it cannot be concluded that the advertisement quality of the first day is higher than that of the second day. The quality of the advertisement is a hidden "value" and the increase in product popularity is an observable "reward". The agent's goal is to select options with higher "values" based on observable "rewards" to maximize his total reward. Besides advertising, the establishment of datasets for large-scale models and the employment of personnel also exhibit the property of diminishing marginal utility.

In this work, we consider the situation where an agent faces a concave aggregated reward function. We define it as the bandits with concave aggregated reward(BCAR) problem. In this model, the reward of pulling any arm decays over time. In our setting, there are agent-unknown random values v(t) and real marginal rewards r(t). The agent-unknown random values v(t) are similar to the rewards in the classic MAB model and sampled in the range (0, 1]. These two values are correlated by an increasing and concave function f(·), i.e., r(t) = f(∑j≤t v(j)) - f(∑j≤t-1 v(j)). The objective of the agent is to maximize his expected total reward E [f (∑Tj=1 vaj (j))] in a time horizon T by carefully pulling arms in each round.

Challenges. (1) Potential sublinear reward: The cumulative reward may not increase linearly with T, so the algorithm with a sublinear regret upper bound may not achieve a reward of (1 - o(1))OPT. (2) Indirect connection between r(t) and v(t): The thorniest one stems from the particular aggregated reward function, namely that the rewards r(t) obtained by sampling cannot reflect the value v(t) of the arms. (3) Nonindependence among selections: The agent's past selections will impact the rewards of future selected arms due to the implicit dependence between arms. As the total reward is not a simple sum of all arm's values in each round, the selection of arms in different rounds is no longer independent.

Contributions. (1) To the best of our knowledge, this is the first work to investigate the bandits with concave aggregated reward. This model formulates the bandit problem associated with diminishing marginal utility. Our algorithms achieve rewards of (1 - o(1))OPT, which existing approaches cannot attain. (2) To tackle this problem, we propose a sliding window based algorithm SW-BCAR with provable regret bound. We prove that the algorithm SW-BCAR attains a regret as ˜O(K1/3T -1/3 )OPT, where K, T and OPT are the number of arms, the number of rounds and the best-arm benchmark. (3) We also study an extended case of the BCAR, where the agent knows that the maximum of the arms' mean values µ∗ is in the range [ 1σ , 1] and σ > 1. We call this case the parameter case. We propose a UCB based algorithm SWUCBBCAR with a provable regret guarantee ˜O(K1/2T -1/2 )OPT. (4) We validate the performance of our algorithms via numerical simulations.

2 ProblemFormulation and Preliminaries

We formally define the bandits with concave aggregated reward(BCAR) as follows. There is an unknown monotonically increasing concave reward function f : R+ → R+. Let K be the set of alternative arms and K = {1, 2, ...,K}. Each arm a is associated with a value distribution Da. Let µ(a) = EX∼Da [X]. All the value distributions are supported in (0, 1]. The game is played T rounds. When the agent chooses one of the arms, the arm will generate a value sampled from its distribution. Formally, the problem protocol at each round t = 1, ..., T is as follows:

• The agent chooses one arm at ∈ K and the arm generates a value vt = vat (t) which is unknown to the agent.

The objective of the agent is to maximize his expected total reward E [f (∑Tj=1 vaj (j))]. Figure 1 illustrates the model of BCAR.

Regret. An algorithm is optimal if it maximizes the expected total reward. We define the optimal expected total reward as OPT = maxa1,...,aT E [f (∑Tj=1 vaj (j))] .

The suboptimal algorithm A are evaluated via the expected total regret: E [RA(T )] = OPT - EA [f (∑Tj=1 vaj (j))] .

Since the reward function may not increase linearly with T in this problem, if an algorithm B attains a sublinear regret E [RB(T)], E [RB(T)] may be Θ(f(T)) and the agent may attain a reward of Θ(1)OPT, which signifies a considerably undesirable outcome. For example, f(x) = logx and E [RB(T)] = O(√T) . To eliminate the effects of the concave aggregated reward function, we consider the ratio of the algorithm's regret and the best-arm

ݕ

benchmark OPT, i.e., E [RA(T)] /OPT, to measure the algorithm performance. For example, if f(x) = logx and E [RA(T )] /OPT = O(√T /T ), the algorithm A attains a regret of O(T -1/2 logT). And the algorithm A is better than an algorithm B that attains a regret of E [RB(T )] = O(√T ). In [Bubeck and Cesa-Bianchi, 2012], Bubeck et al. proved that in the Stochastic MAB problem, fix round number T and arm number K, for any bandit algorithm, there exists a problem instance such that E[R(T)] ≥ Ω(√KT) and E[R(T )] OPT = E[R(T)] O(T) ≥ Ω (K1/2T -1/2 ). Because the stochastic MAB is equivalent to the case where f(x) = x in the BCAR problem, it is a sub-problem of our model. The algorithm designed for the BCAR problem should also apply to the stochastic MAB. We can prove the following theorem:

Theorem 1. In the BCAR problem, fix round number T and arm number K, for any bandit algorithm, there exists a problem instance such that

We summarize key notations used throughout this paper in Table 1.

3 Fundamental Case

The model is a variant of the classical stochastic multi-armed bandit problem [Lai et al., 1985], motivated by diminishing rewards. In this problem, the learner cannot observe the value sampled from the selected arm's distribution. However, the observed diminishing reward is a concave function of the value of the action currently chosen and the values generated by the past actions. The learner's goal is to design a policy to find the optimal arm quickly from observed rewards to maximize the aggregated reward or minimize the regret.

In this problem, even if the aggregated reward function is a Lipschitz function, i.e., ∃L ∈ R s.t. |f(x+y)-f(x)| ≤ L·|y|, ∀x, y ∈ R, existing algorithms, for example UCB1[Auer et al., 2002a], can only attain a regret as ˜O (√KTL). However, the reward function does not correlate linearly with the round number T. So, if an algorithm attains the regret sublinear in T, the algorithmmay achieve a regret of Θ(1)OPT, which signifies a considerably undesirable outcome.

In order to address the BCAR problem, we propose the SW-BCAR algorithm. Our algorithm aims to detect arms with small mean values through a period of exploration, after which these "bad" arms will be abandoned and excluded from further selection. The arms that have not been abandoned are referred to as reserved arms. For further convenience, we introduce the following definitions:

Definition 1. Let Kend be the set of arms reserved at the end and a∗end be the arm with the maximum mean value in Kend. Let µ∗end = µ(a∗end ). We define bad arms to be the arms whose mean values are less than µ∗end and good arms to be the arms whose mean values are not less than µ∗end .

Definition 2. Let weight wt in round t be the ratio between the reward obtained in round t and the value generated by the chosen arm in round t, i.e. wt = rat (t) vat (t) .

Key idea. Initially, we use a round-robin approach to select arms from the arm set, and a sliding window approach to reduce the impact of the concave aggregated reward function on our assessment of arm mean values. When an arm is selected, the reward is determined by both the value generated by the chosen arm and the weight determined by the aggregated function. As the value of the aggregated function increases, the slope may gradually decrease, indicating that the weight may decrease as the selection process progresses. If the weights of an arm at different rounds vary significantly, our evaluation of the arm's mean value may be imprecise. To address this, we employ a sliding window-based approach to ignore the rewards in the early rounds, thereby reducing the impact of weight differences on arm assessment. We assume that there are two arms a and a′ , where µ(a) > µ(a′ ). If the agent is unable to determine which arm has a lower mean value, he can deduce that the lower bound of the change rate of weights is linearly related to µ(a)-µ(a′ ). In this way, the agent can ensure that the regret is bounded even when more rounds of exploration are undertaken.

To minimize the regret upper bound according to its expression, we choose an appropriate length of the sliding windows denoted as m. We can prove that when m =

Algorithm 1: SW-BCAR

Input: K, T 1 Initialize the set of arms K; m ← ⌈(T/K)2/3 log1/3 T ⌉; 2 Build a circular linked list B on A, a vector C ∈ NK×K , count vectors D, E, N ∈ NK ; 3 Initialize all items in C and D,E,N to 0, a1 = 1; 4 for round t = 1, 2, ...,Km do 5 pick arm at in B, receive rt; Nat ←Nat +1; rNat at ← rt; at+1 ←next(at) in B; 6 end 7 for arm j ∈ [1,K] do 8 rj ← 1m ∑Nj n=Nj-m+1 rn j ; 9 end 10 for round t =Km+1,Km+2, ..., T do 11 pick arm at in B, receive rt; Nat ←Nat +1; rNat at ← rt; rat ← 1m ∑Nat n=Nat -m+1 rn at ; 12 for arm j ∈ B do 13 if Cat,j ̸=m and rat > rj then 14 Cat,j ← Cat,j + 1; 15 if Cat,j = m then 16 Dat ← Dat + 1; Ej ← Ej + 1; Remove-Arms(D,E,B); 17 end 18 end 19 if Cat,j ̸=m and rat ≤ rj then 20 Cat,j ← 0; 21 end 22 end 23 at+1 ←next(at) in B; 24 end

⌈(T/K)2/3 log1/3 T⌉, we can minimize the regret upper bound.

Arm a and a′ are two arms in the arm set K. For all i ∈ {1, ..., T}, we define that a′ is i-better than a if the following requirements are met: 1) for all j ∈ {1, ..., i}, we denote the weight multiplied by the value of arm a in it's j-th latest selection as ˆwj. We denote the weight multiplied by the value of arm a′ in it's j-th latest selection as ˆw′j . For all j ∈ {1, ..., i}, ˆwj ≥ ˆw′j ; 2) when the event in 1) occurs, we compare the mean reward of the latest i selections of arm a and that of arm a′ . We call these comparisons as i-mean value comparisons. For these comparisons, there are i consecutive comparisons satisfy that the mean reward of the latest i selections of arm a is lower than that of arm a′ . For arms a and a′ , we define that a is i-worse than a′ if a′ is i-better than a. When an arm a is m-better than half of the other reserved arms, the agent will abandon all the arms that are m-worse than a; when an arm is m-worse than more than half of the other reserved arms, the agent will abandon the arm a.

The details of SW-BCAR are shown in Algorithm 1. It is composed of three phases:

• Initial phase (line 1-3): Let the parameter m =

Algorithm 2: Remove-Arms

Input: D, E, B 1 flag ← 1; 2 while flag = 1 do 3 f lag ← 0; 4 for arm j, a ∈ B do 5 if Dj ≥ |B|/2 and Cj,a = m then 6 remove a from circular linked list B; Update D, E; f lag ← 1; 7 end 8 if Ej ≥ |B|/2 then 9 remove j from circular linked list B; Update D, E; f lag ← 1; 10 end 11 end 12 end

⌈(T/K)2/3 log1/3 T⌉. The agent maintains a count vector C ∈ NK×K , where Ca,a′ is used to record the number of consecutive comparisons satisfy that the mean reward of the latest m selections of arm a is larger than that of arm a′ for the m-mean value comparison. When Ca,a′ = m, it will no longer change. In addition to this, the agent maintains three other vectors D, E, N ∈ NK . Da, where a ∈ K, is the number of the reserved arms which is m-worse than arm a. Ea, where a ∈ K, is the number of the reserved arms which is m-better than arm a. Na, where a ∈ K is the number of arm a has been pulled. The agent initializes all items in all vectors to 0. B is a circular linked list of reserved arms.

• Exploration phase (line 4-9): The agent uses round robin to select each arm m times and calculates the mean reward for each arm in this phase.
• Sliding window phase (line 10-24): The agent puts all the arms that have not been abandoned yet into the reserved arm set and then uses round robin to select arms from this set in future. When the agent selects an arm at, he will calculate the mean reward of the arm at's latest m selections and then

compare it with the other reserved arms' mean rewards of their latest m selections and update Cat,a′ , Dat and Ea′ for all a′ in the reserved arms, where a′ ̸= at. When an arm a is m-better than half of the other reserved arms, the agent will abandon all the arms that are m-worse than a; when an arm is m-worse than more than half of the other reserved arms, the agent will abandon the arm a. By removing the arms in this way, we can have a good performance guarantee for µ∗end and limit regret due to abandoning the largest mean value among the reserved arms.

In the rest of this section, we will prove the regret bound of Algorithm 1. Let va(t) and ra(t) be the value and reward generated by the arm a ∈ K when it is selected for the t-th time. Let wa(t) = ra(t)/va(t) and wt = wat (t). We can know that ∀t1 < t2, t1, t2 ∈ {1, · · · , T}, wt1 ≥ wt2 .

Let ra(t), where t ≥ m, be the mean reward generated by the latest m choices of the arm a (from its (t - m + 1)-th choice to its t-th choice), i.e. ra(t) = 1m ∑ti=t-m+1 ra(i). Let va(t), where t ≥ m, be the mean value generated by the latest m choices of the arm a, i.e. va(t) = 1m ∑ti=t-m+1 va(i). We then estimate the deviation of the average from the true expectation. By defining the confidence radius ˆ δt(a) = 2wa(t)√ 2 log T m , we have ∀i ∈ {t - m + 1, ..., t}, ra(i) ≤ wa(i) ≤ wa(t - m + 1), i.e. ra(i) ∈ (0,wa(t -m+ 1)]. From Azuma-Hoeffding's inequality, we can show that

Similarly, let δ′ = √ 2 logT m , from Hoeffding's inequality, we have

Definition 3. We define the good event to be the event that (2) and (3) hold for all arms and all rounds simultaneously. Let "bad event" be the complement of the good event.

We will analyze the regret for the good event and the bad event separately. We note that if a lousy arm is preserved, the slope of the reward function will change fast. Then, we have the following result:

Theorem 2. There are K alternative arms and T rounds. For the bandits with concave aggregated reward, SW-BCAR algorithm achieves regret for the BCAR bounded by

Proof Sketch. From the properties of concave functions, we can infer that f(µ∗T ) ≥ OPT. We first analyze the difference between the total revenue and f(µ∗T), and then convert the result to a bound on the regret.

Although the proof for Theorem 2 is complicated, the key is to divide the regrets generated by SW-BCAR into three categories and analyze them separately: 1) In good events, the regrets generated by the algorithm as the agent selects the bad arms, denoted as ˆR1; 2) In good events, the regrets generated by the algorithm as the agent removes the good arms, denoted as ˆR2; 3) In bad events, the regrets generated by the algorithm, denoted as ˆR3.

First, we give the upper bound of E[ ˆR1]. We prove that

if a lousy arm is not abandoned on time, E[rat (t)] µ(at) changes fast as selections progress. Then we prove that the regret bound for BCAR generated by the "bad arms", E [ ˆR1 ] = O (T -1/3 (K logT)1/3 logK) f(µ∗T). Second, we give the upper bound of E[ ˆR2]. We prove that in good events µ∗ - µ∗end < O(δ′ logK). Then, we prove that the regret bound for BCAR generated by the "good arms", E [ ˆR2 ] = O (T -1/3 (K logT)1/3 logK) f(µ∗T). Then, we give the upper bound of E[ ˆR3]. Since the probability of bad events happening is O( 1 T 2 ), we can prove that the regret bound for

By summing up the above results and converting them to an analysis of the regret, we are able to complete the proof.

4 Parametric Case

In the previous section, we discuss the fundamental case. Since both the reward function and the value distribution of each arm are unknown, it is difficult for us to analyze the slope range of the function and the actual distribution of arms. In many applications, although we do not know the mean value of the optimal arm, we know that it has a constant lower bound.

In this section, we consider the parametric case. In the BCAR model, assume that there is a parameter σ > 1. We define the optimal arm a∗ as the arm with the largest mean value and µ∗ = µ(a∗ ), where µ∗ is in the range of [ 1σ , 1].

We propose a variant of Algorithm 1 named SWUCBBCAR to solve the problem in this situation. This algorithm also uses the upper/lower confidence bound method and attains a regret as ˜O(K1/2T 1/2 ) f(µ∗ T) µ∗ T . Since E[ ˆR(T)] ≥ Ω(√KT), Algorithm 3 is asymptotically optimal. The pseudo algorithm for this method is given by Algorithm 3.

Similar to the proof of Theorem 2, we can prove the following theorem:

Theorem 3. For the bandits with concave aggregated reward in the parametric case, SWUCB-BCAR algorithm achieves regret for the BCAR bounded by

Proof Sketch. For each arm a ∈ K, let ∆(a) = µ∗-µ(a) µ∗ be the difference between the mean value of the optimal arm a∗ and the mean value of the arm a(a ̸= a∗ ). Let ma = ⌈ 8 logTσ2 ∆(a)2 ⌉. For each arm a ∈ K, let Ra (T) be the regret generated by the difference between the arm a and a∗ . Let fa be the reward generated by arm a. Similar to the proof of Theorem 2, we have E[Ra (T )] ≤ O ( σ2 µ∗ log2 T ∆(a) ) f(µ∗ T) µ∗ T . Let us fix some ϵ > 0; then regret consists of two parts: 1) All arms a with ∆(a) ≤ ϵ contributes at most a total

Algorithm 3: SWUCB-BCAR

Input: K, T

• 1 Initialize the set of arms K;

of ϵµ∗Tf ′end ; 2) each arm a with ∆(a) > ϵ contributes at most a total of O ( µ∗Kσ2 log2 T ϵ ) · f(µ∗ T) µ∗ T . Combining these two parts, in good events we have E[R(T)] ≤ O(ϵµ∗T + µ∗Kσ2 log2 T ϵ ) f (µ∗ T ) µ∗ T . Let ϵ = √TKσ logT. By summing up the above results, we can complete the proof.

5 Evaluation By Simulation

In this section, we evaluate our algorithms' effectiveness in terms of regrets. We compare the performance of SW-BCAR and SWUCB-BCAR with benchmark algorithms.

We use UCB1 [Auer et al., 2002a] and exp3 [Auer et al., 2002b] for comparison. Both of them are the most classic bandits algorithms. Besides, we use Rless [Metelli et al., 2022] and AAEAS [Lykouris et al., 2020] for comparison. Both of them are the algorithms for the non-stationary bandits. The algorithm AAEAS is used to tackle the bandits with adversarial scaling. The algorithm Rless is used to tackle the stochastic rising bandits. These bandit models are similar to the BCAR model. All of the four algorithms require a range of rewards in each round. Although our algorithms do not require such a setting, to facilitate the comparison, we use the aggregated reward functions satisfying the Lipschtiz assumption. Specifically, we use the following reward functions with different parameters: (1)f1,c(x) = c - c · e(-x/c) , c > 0; (2)f2,c(x) = [log(1 + cx)]/c, c > 0; (3)f3,c(x) = (1 + x)1/c - 1, c ≥ 1. Here we mainly consider the truncated normal distributions and the reward function f3,c(·) to evaluate the algorithms' performance.

We set the variance of all truncated normal distributions in the experiment to 0.2, and designed several different sets of experiments to study the effect of variables on the algorithms. All results are the averages over 20 runs. In the experiments, variables other than specified separately were fixed as follows: 1) the round number T = 20000; the arm number K = 2; 2) the optimal arm's mean value µ∗ = 0.8; the suboptimal arms' mean values µ(a) = 0.4; 3) the aggregated reward function f(x) = √1 + x-1; 4) the parameter for the value range σ = 2.

Impact of Round Number. Figure 3 presents the impact of round number on algorithms' regrets. As shown in Figure 3, SW-BCAR and SWUCB-BCAR can always obtain better results than the benchmark algorithms in the considered situations. As T increases, the regrets of other methods will increase faster than that of our algorithms. In Figure 3(b) and Figure 3(d), as T grows, the ratio between the regrets attained by our algorithms and the optimal reward gradually decreases. At the same time, the ratio between the regrets attained by the benchmark algorithms and the optimal reward is almost unchanged. We calculate that the attained total regrets of our algorithms are at least 79.38% lower than those of the benchmark algorithms, when T ≥ 20000 and K = 2. In Figure 3(a) and Figure 3(c), the regret for SWUCB-BCAR decreases with T. In our problem, the reward function is a monotonically increasing concave function. Although µ∗T -∑Tt=1 va(t)(t) increases as T increases, f(µ∗T) - f(∑Tt=1 va(t)(t)) does not necessarily increase as T increases. An illustrative example is √1.21 - √1 ≥ √4.31 - √4. We can establish that the experimental results align with the theoretical analysis.

Impact of Reward Function. Figure 4 presents the impact of different aggregated reward functions on algorithms' regrets. The larger the function parameter c is, the faster the slope of the function changes as its input changes. When c = 1, i.e. f(x) = x, this problem degenerates into the Stochastic MAB Problem. The algorithm UCB1 and exp3 which are designed specifically for this situation have lower regret than SW-BCAR and SWUCB-BCAR. The results are within our expectations. When the function's slope varies rapidly with its input, SW-BCAR and SWUCB-BCAR attain a smaller regret than other algorithms. Furthermore, our algorithms can provide an excellent performance guarantee no matter how the reward function changes. These experimental results also verify our algorithm's effectiveness on the BCAR. We calculate that the attained total regrets of our algorithms are at least 67.96% lower than those of the benchmark algorithms, when c ≥ 1.4.

Impact of MeanValue. Figure 5 presents the impact of the suboptimal arm's mean value on algorithms' regret. In these simulations, we find that SW-BCAR and SWUCB-BCAR can always obtain better result than benchmark algorithms. The cost of selecting the wrong arm decreases as the mean of the suboptimal arm increases. Consequently, various algorithms can yield satisfactory results in this scenario. Conversely, when the suboptimal arm mean is small, SW-BCAR and SWUCB-BCAR surpass other algorithms by achieving significantly better rewards.

Impact of Parameter for the Value Range. Figure 6 presents the impact of the parameter for the value range on algorithms' regret. As shown in Figure 6, for parameters that meet the requirements, the closer they are to 1 µ∗ , the smaller regrets SWUCB-BCAR will obtain. As the parameter becomes larger, SWUCB-BCAR requires more rounds to distinguish the optimal arm. A small round number is not enough for the agent to distinguish which arm is better, thus the algorithm cannot obtain a satisfactory result. When T is large enough, R(T)/OPT will gradually decrease as T increases.

6 RelatedWork

The Bandits with Concave Reward Functions. Some models have been proposed for formulating bandits with concave reward functions [Agrawal and Devanur, 2014; Xu et al., 2020]. However, in these models the arm values and the concave functions are assumed to be known, which significantly decreases the complexity of the problem.

The Stochastic MAB Problem. In the stochastic MAB problem [Gittins, 1979], when the agent chooses an arm a, he will receive a stochastic reward, which is sampled independently from an unknown distribution. The two most representative solutions for this problem are UCB [Gittins, 1979] method and Thompson sampling [Thompson, 1933]. Both methods give a regret bound of E[R(T)] ≤ √KT logT. In our model, the concave aggregated reward function introduces additional complexity into the problem and requires development of different strategies to effectively solve it.

The Adversarial MAB Problem. In the adversarial MAB problem [Auer et al., 2002b; Mohri and Yang, 2016; Saha and Tewari, 2011; Scaman et al., 2017; van der Hoeven et al.,

2020; Lykouris et al., 2020], an adversary possesses the ability to manipulate the reward associated with each arm[Hazan and Kale, 2011]. One of the most widely employed algorithms to address this problem is the exp3 algorithm[Auer et al., 2002b], which achieves a regret of O(√KT logK) in this model. However, the regret fails to completely meet the agent's requirements in our model.

The Non-stationary Stochastic MAB problem. In the non-stationary stochastic MAB problem[Russac et al., 2019; Besbes et al., 2014; Trov`o et al., 2020; Garivier and Moulines, 2008], the mean reward of each arm changes over time. In the restless bandits[Whittle, 1988], the reward distributions change in each round, but the agent is aware of these changes. In the rested bandits[Tekin and Liu, 2012], an arm's reward distribution changes only when it is chosen by the agent. In the rotting bandits[Levine et al., 2017], the reward of each arm decays with the number of times it is selected, and the algorithm SWA achieves a regret as ˜O(K1/3T 2/3 ). In the bandits with adversarial scaling[Lykouris et al., 2020], rewards consist of two components: the random values generated by the arms and the "scaling" determined by an adversary. The algorithm AAEAS attains a regret as O (∑a̸=a∗ k log(kT ) ∆(a) ) in this model. In the stochastic rising bandits[Metelli et al., 2022], the expected rewards of arms are determined by the number of times they have been pulled or the current round number. In this model, The algorithmRless attains a regret as ˜O(T 2/3 ).

In our model, the aggregated reward function introduces two novel challenges that must be addressed: 1) the rewards obtained from the agent's previous selections have an impact on his future rewards, and 2) the cumulative reward may not increase linearly with the round number T . Even if the agent employs existing methodologies and attains a regret that is sublinear with respect to T , we are unable to provide a theoretical proof regarding the agent's ability to attain a reward of (1 - o(1))OPT . However, by utilizing our proposed methods, we are able to establish a theoretical proof that the agent can achieve a reward of (1 - o(1))OPT in this problem.

7 Conclusion

In this study, we proposed a novel bandit framework named the Bandits with Concave Aggregated Reward. To address this problem, we developed a sliding-window type algorithm SW-BCAR, and proved that the regret is upper bounded by ˜O(K1/3T -1/3 )OPT. Additionally, for the parameter case, we proposed another algorithm SWUCBBCAR, and we also proved that the regret is upper bounded by ˜O(K1/2T -1/2 )OPT, which matches the optimal regret bound for this problem. Our framework and results provide a starting point for further exploration of the BCAR problem. There are several intriguing questions that remain for further research. One is to establish a lower bound on the regret for the fundamental case. Another question is to study a general MAB under additional constraints such as budget limits and combinatorial bandits. Furthermore, extending the optional range from an arm set to a d-dimensional space is also an inspiring and significant problem that awaits to a solution.

Acknowledgements

The research is partially supported by National Key R&D Program of China under Grant No. 2021ZD0110400, Innovation Program for Quantum Science and Technology 2021ZD0302900 and China National Natural Science Foundation with No. 62132018, 62231015, "Pioneer" and "Leading Goose" R&D Program of Zhejiang, 2023C01029, and 2023C01143, Fundamental Research Funds for the Central Universities WK2150110024, and Key Laboratory of Internet and industrial integration and innovation (CAICT), MIIT.