BORA Bayesian Optimization for Resource Allocation

2025-04-27 0 0 607.74KB 31 页 10玖币

侵权投诉

Highlights

BORA: Bayesian Optimization for Resource Allocation

Antonio Candelieri, Andrea Ponti, Francesco Archetti

•Using Bayesian Optimization as a more eﬀective and eﬃcient approach

than semi-bandit feedback to solve the optimal resource allocation

problem

•Extending the original formulation of the optimal resource allocation

problem to a more general setting, with the aim to address new real-life

problems

•Evaluating the beneﬁts of three diﬀerent implementations of the pro-

posed approach on a test problem (from the semi-bandit feedback liter-

ature) and a real-life setting (i.e., optimal resource allocation in multi-

channel marketing).

arXiv:2210.05977v1 [cs.LG] 12 Oct 2022

BORA: Bayesian Optimization for Resource Allocation

Antonio Candelieria, Andrea Pontia,c, Francesco Archetti1

aDepartment of Economics, Management and Statistics, University of

Milano-Bicocca, Building U7, via Bicocca degli arcimboldi 8, Milan, 20126, Italy

bOAKS s.r.l., Milan, 20125, Italy

cDepartment of Computer Science, Systems and Commuinication, University of

Milano-Bicocca, Building U14, viale Sarca, 336, Milan, 20126, Italy

Abstract

Optimal resource allocation is gaining a renewed interest due its relevance as

a core problem in managing, over time, cloud and high-performance comput-

ing facilities. Semi-Bandit Feedback (SBF) is the reference method for eﬃ-

ciently solving this problem. In this paper we propose (i) an extension of the

optimal resource allocation to a more general class of problems, speciﬁcally

with resources availability changing over time, and (ii) Bayesian Optimiza-

tion as a more eﬃcient alternative to SBF. Three algorithms for Bayesian

Optimization for Resource Allocation, namely BORA, are presented, work-

ing on allocation decisions represented as numerical vectors or distributions.

The second option required to consider the Wasserstein distance as a more

suitable metric to use into one of the BORA algorithms. Results on (i)

the original SBF case study proposed in the literature, and (ii) a real-life

application (i.e., the optimization of multi-channel marketing) empirically

prove that BORA is a more eﬃcient and eﬀective learning-and-optimization

framework than SBF.

Keywords: Optimal Resource allocation, Semi-Bandit Feedback, Bayesian

Optimization, Gaussian Processes, Kernel, Wasserstein distance.

1. Introduction

1.1. Motivation

The reference problem considered in this paper is the optimal sequential

resource allocation. Assume that, at each time-step t, a decision-maker has

to distribute a given budget ¯

b(t)over mdiﬀerent options with the aim to max-

imize the cumulative reward of her/his decisions in Ttime-steps. Formally,

Preprint submitted to Nuclear Physics B October 13, 2022

she/he wants to solve the following optimization problem:

max

x(t)∈Rm

E"T

t=1

fx(t)#

s.t.

i=1

x(t)

i≤¯

b(t)

(1)

where fx(t)is the immediate reward associated to the decision x(t)

made at time t. In some cases the constraint in (1) is considered as an

equality instead of an inequality (i.e., all the budget must be used), as done

later in this paper.

Optimal (sequential) resource allocation is a well known problem in op-

eration research, with traditional examples such as inventory management,

portfolio allocation, etc. [1, 2, 3, 4]. Some approaches are related to stochas-

tic optimization (e.g., multi-period and multi-stage stochastic optimization

[5, 6]), but the most relevant literature for this paper is from Multi Armed

Bandit (MAB) [7, 8], speciﬁcally the semi-bandit feedback (SBF) [9, 10, 11,

12, 13, 14]. SBF has recently gained a renewed interest according to the tech-

nological advances and widespread usage of cloud and/or high performance

computing facilities [15, 16, 17, 11, 18], where it is critical to optimally allo-

cate computational resources (i.e., the budget) to diﬀerent jobs (i.e., options,

arms) with the aim to maximize the number of successfully completed jobs

over time. Analogously to MAB, also in SBF the learning process requires

that every decision x(t)must be taken by balancing between exploitation

(i.e., making the best decision according to the current knowledge about the

problem) and exploration (i.e., making a decision with the aim to reduce un-

certainty instead of settling for the currently known best one). While MAB

consists in selecting, at each step t, just one option (aka arm) among the m

possible, SBF allows to simultaneously choose multiple arms, by allocating

a diﬀerent amount x(t)

i≥0 of the available budget on each of them. The

reward will depend on the amount of budget allocated on the diﬀerent arms,

altogether. It is also important to remark the diﬀerence with Combinatorial

MAB (CMAB), where more than an arm can be pulled at each time-step

(like in SBF), but decision variables, x(t)

i, are binary insetad of numeric [11].

In the original formulation of optimal resource allocation through SBF,

proposed in [19] and successively improved in [20], the options are computer

processes (aka jobs), the budget is constant over time and rescaled to 1 so

that the constraint becomes Pm

i=1 x(t)

i≤1 and, consequently, x(t)represents

the allocation, in percentage, of the resources to the mdiﬀerent computer

processes at time-step t. Accordingly, the immediate reward is the number of

successfully completed processes, whose individual probabilities of comple-

tion are given by Bernoulli distributions with unknown parameters x(t)

i/νi,

that is fx(t)=Pm

i=1 Bx(t)

i/νi. Since values ν1, ..., νmare unknown, the

immediate reward is black-box. It is also important to clarify that, at the

end of every time-step, the resources are replenished and all jobs are reset

regardless of whether or not they completed in the previous time-step (i.e.,

there is not any inter-temporality between consecutive decisions).

Indeed, the aim is to learn, as fast as possible, the values ν1, ..., νm, in or-

der to choose x(t)maximizing EhPT

t=1 Pm

i=1 Bx(t)

i/νii, with Pm

i=1 x(t)

i≤1.

Another well-known learning-and-optimization framework is Bayesian Op-

timization (BO), a sample eﬃcient sequential model-based global optimiza-

tion method for expensive, multi-extremal, and possibly noisy functions [21,

22, 23]. As MAB, BO is sequential and deals with the exploitation-exploration

dilemma; the main diﬀerence among these two methods – at least in their

original formulations – is that MAB optimizes over a discrete search space

(i.e., every decision is the selection of an arm among m), while BO opti-

mizes over a continuous search space (i.e., every decision is a point of a

box-bounded continuous space). However, the learn-and-optimize underly-

ing nature of the two methods is so close that BO can be considered “a MAB

with inﬁnite arms”, so that convergence proofs and results from MAB are

often used to also prove convergence of BO methods, such as in [24]. More

speciﬁcally, consider the following global optimization problem:

max

x∈Ω⊂Rmf(x) (2)

and denote with r(t)=f(x∗)−fx(t)the so called instantaneous regret,

that is the diﬀerence between the actual (unknown) optimum f(x∗) and the

immediate reward observed for the t-th decision. Then, denote with R(T)=

t=1 r(t)the cumulative regret; [24] proved that, under suitable conditions,

the cumulative regret of BO is sub-linear, meaning that lim

T→∞

R(T)

T= 0.

This means that, if we could remove the constraint in (1) and impose

x(t)∈Ω,∀t={1, ..., T }, then solving (2) via BO would lead to a solution

for the unconstrained version of the problem (1). Consequently, a simple

idea would be to address the problem (1) via Constrained BO (CBO) [25,

26, 27, 28], with ¯

b(t)potentially changing at each time-step t. Although

possible, we are going to demonstrate that the CBO approach is not so

eﬃcient, and therefore we propose a novel method performing BO over the

m−1 dimensional simplex, ∆m−1, requiring to work over univariate discrete

probability measures instead of points in an m-dimensional box-bounded

search space. The basic idea is that we are interested in searching for the

optimal distribution of the currently available budget, independently on its

amount.

1.2. Contributions

•extending the initial formulation of the optimal resource allocation

problem [19, 20] to the case of (i) budget changing over time, that

is ¯

b(t), and (ii) and equality constraint, that is Pi=1:mx(t)

i=¯

b(t). The

ﬁrst aspect is a requirement emerging from real-life applications where

the budget ¯

b(t)cannot be directly decided by the decision-maker, but

it comes out from other ﬁnancial/commercial/managing decision pro-

cesses. The second aspect represents the assumption that the entire

budget must be allocated.

•a BO approach for optimal sequential resource allocation – namely,

BORA: Bayesian Optimization for Resource Allocation – as an eﬀective

alternative to SBF.

•identiﬁcation of classes of problems which can be eﬀectively and eﬃ-

ciently solved through the proposed BORA algorithm(s).

1.3. Related works

A survey on Optimal Resource Allocation is given in [29]. Although not so

recent, it provides a relevant overview about application domains and solving

strategies. As far as the SBF methodology is concerned, many papers can be

found in the recent literature, such as [9, 10, 11, 12, 13, 14]. With respect to

its speciﬁc application to the optimal resource allocation problem, the most

relevant references are [19, 30, 20, 31, 32]. Finally, other related works regard

the topic of BO, especially Constrained BO (CBO), such as [25, 26, 27, 28].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

HighlightsBORA:BayesianOptimizationforResourceAllocationAntonioCandelieri,AndreaPonti,FrancescoArchettiUsingBayesianOptimizationasamoreeectiveandecientapproachthansemi-banditfeedbacktosolvetheoptimalresourceallocationproblemExtendingtheoriginalformulationoftheoptimalresourceallocationproblemtoam...

展开>> 收起<<

BORA Bayesian Optimization for Resource Allocation.pdf

共31页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

BORA Bayesian Optimization for Resource Allocation

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: