Abstract: Many budget-related multi-armed bandit models have been proposed,but the practical problems they can solve are limi-ted,that is,they must all be subject to a total budget limit.Therefore,this paper proposes a multi-armed bandit model based on time-variant budgets,which can break this limitation and be used to solve other practical problems.The model captures the situation where the learner’s actions for each round are limited by the corresponding round budget.More specifically,at each round,the player is required to choose to pull L(L≥1) arms(L is not a fixed value) within the budget limits of that round.The player’sgoal is to maximize the total average reward within the budget limits of each round.According to this model,a dynamic programming algorithm based on confidence bound is proposed.The algorithm takes advantage of the characteristics of the model,takes the confidence upper bound of the empirical average reward of the arm as the basis for each round,and then uses the dynamic programming algorithm to perform the arm pull operation.In this paper,the concept of regret is introduced,and it is deduced theoretically that there is a relationship between the upper bound of regret and the sum of budget.Finally,the feasibility of the proposed algorithm is verified by comparing the proposed algorithm with other traditional budget-limited multi-armed bandit algorithms(ε-first,KUBE,BTS) under different scenarios.

Key words: Multi-armed bandit, Time-variant budgets, Empirical average reward, Dynamic programming, Regret