Fully Dis ibu ed Bayesian Op imiza ion wi h S ochas ic Policies
Ja ie Ga cia-Ba cos1and Ruben Ma inez-Can in1,2
1Ins i u o de In es igacion en Ingenie ia de A agon, Uni e si y o Za agoza
2Cen o Uni e si a io de la De ensa, Za agoza
jgba cos, mcan in@uniza .es
Abs ac
Bayesian op imiza ion has become a popula
me hod o high- h oughpu compu ing, like he
design o compu e expe imen s o hype pa ame-
e uning o expensi e models, whe e sample e -
ficiency is manda o y. In hese applica ions, dis-
ibu ed and scalable a chi ec u es a e a necessi y.
Howe e , Bayesian op imiza ion is mos ly sequen-
ial. E en pa allel a ian s equi e ce ain compu-
a ions be ween samples, limi ing he pa alleliza-
ion bandwid h. Thompson sampling has been
p e iously applied o dis ibu ed Bayesian op i-
miza ion. Bu , when compa ed wi h o he acqui-
si ion unc ions in he sequen ial se ing, Thomp-
son sampling is known o pe o m subop imally. In
his pape , we p esen a new me hod o ully dis-
ibu ed Bayesian op imiza ion, which can be com-
bined wi h any acquisi ion unc ion. Ou app oach
conside s Bayesian op imiza ion as a pa ially ob-
se able Ma ko decision p ocess. In his con ex ,
s ochas ic policies, such as he Bol zmann policy,
ha e some in e es ing p ope ies which can also be
s udied o Bayesian op imiza ion. Fu he mo e,
he Bol zmann policy i ially allows a dis ibu ed
Bayesian op imiza ion implemen a ion wi h high
le el o pa allelism and scalabili y. We p esen e-
sul s in se e al benchma ks and applica ions ha
show he pe o mance o ou me hod.
1 In oduc ion
Many enginee ing p oblems and scien ific phenomena a e be-
ing s udied in high- h oughpu compu ing acili ies, h ough
complex compu e models o simula o s. Due o he la ge
amoun o esou ces ha a e needed, expe imen s should be
ca e ully selec ed and s udied. This is known as he design
and analysis o compu e expe imen s [Sacks e al., 1989].
Bayesian op imiza ion (BO) can be used o designing com-
pu e expe imen s which equi e he sea ch o an op imum
alue [Jones e al., 1998; Mockus e al., 1978]. BO ca e-
ully selec s he nex expe imen s o pe o m in o de o find
he op imum alue as e ficien ly as possible. Fo example,
conside he p oblem o finding he op imal shape o a wing
p ofile o educe he d ag o ce. Ins ead o dealing wi h he in-
amous equa ions o Na ie -S okes, we can expe imen wi h
a Compu a ional Fluid Dynamics (CFD) simula o and check
he ou come [Fo es e e al., 2006; Ma inez-Can in, 2019].
Thus, o he op imiza ion algo i hm, he simula o becomes a
black-box whe e we only ca e abou he esul ing d ag o ce.
Fo scien ific expe imen s, we may wan o adjus he pa am-
e e s o a compu a ional model o cell mig a ion o mimic
he beha iou o in i o o in i o expe imen s [Me ino-
Casallo and o he s, 2018], o we may wan o find new
d ugs h ough i ual sc eening [He nandez-Loba o e al.,
2017]. Finally, one o he mos popula applica ions o BO
is he uning o hype pa ame e s o complex machine lea n-
ing models, such as deep neu al ne wo ks [Snoek e al., 2012;
Klein e al., 2017].
BO achie es sample e ficiency by lea ning a p obabilis ic
su oga e model o he he a ge unc ion. Then, using se -
e al heu is ics, called acquisi ion unc ions, we can selec he
nex poin o be e alua ed o expe imen ed. The e o e, BO
is in insically a sequen ial p ocess. Each new obse a ion
is inco po a ed in o he su oga e model, which a he same
ime, modifies he acquisi ion unc ion o he selec ion o
u u e expe imen s. The e a e ce ain algo i hms ha allow
pa allel o ba ch que ies o expe imen s [Snoek e al., 2012;
Gonz´
alez e al., 2016a; Desau els e al., 2014], bu hey s ill
equi e he que ies o be compu ed in a sequen ial manne .
In high- h oughpu sys ems, hese me hods equi e a cen al
node ha compu es and dispa ches he que ies. Fu he mo e,
as poin ed ou by [Kandasamy e al., 2018], many o hose
me hods do no allow o asynch onous execu ion. To he
au ho s knowledge, only he Thompson sampling app oach
om [He nandez-Loba o e al., 2017]can be ully dis ibu ed.
Howe e , i is well-known ha he e a e many o he acquisi-
ion unc ions ha pe o ms be e han Thompson sampling
in p ac ice [Shah ia i e al., 2016]. In his wo k, we in oduce
a new me hod o allow a ully dis ibu ed BO, which can be
combined wi h any acquisi ion unc ion.
Howe e , he con ibu ion o ou pape is wo old. Be o e
in oducing ou dis ibu ed BO algo i hm, we p esen a new
po ayal o BO in he Ma ko decision p ocess amewo k,
ollowing he analysis o [Toussain , 2014]. We show how
his new amewo k allows a g ea e unde s anding o he ea-
u es and capabili ies o BO. Then, we in oduce he idea o
s ochas ic policies o BO, which is he ing edien necessa y
P oceedings o he Twen y-Eigh h In e na ional Join Con e ence on A ificial In elligence (IJCAI-19)
2357
o pe o m ully dis ibu ed BO in combina ion wi h any ac-
quisi ion unc ion. Fu he mo e, we analyze he ad an ages
o he s ochas ic policies beyond pa alleliza ion, om a heo-
e ical and p ac ical poin o iew.
2 The Op imiza ion Agen
We conside he op imiza ion algo i hm as an agen ha is
in e ac ing wi h he en i onmen , which is he space o unc-
ions. The cu en s a e o he en i onmen is he a ge unc-
ion . The agen does no ha e ull obse abili y o he s a e
and can only pe o m pa ial obse a ions by que ying he
unc ion y = (x ). As poin ed ou in [Toussain , 2014],
he u u e decisions made by he agen can be modelled as a
pa ially obse able Ma ko decision p ocess (POMDP). A
simila analogy, al hough om a con ol heo y pe spec i e is
also p esen ed in [Lam e al., 2016].
2.1 POMDPs
A (PO)MDP is a s ochas ic model whe e he agen and he en-
i onmen a e ully ep esen ed by s a e a iables s ∈Sand
he agen can change ha s a e by pe o ming ac ions a ∈A
in a Ma ko ian way p(s +1|a ,s
). The (PO)MDP model
also assumes ha he agen is a ional, ac ing o maximize
he u u e expec ed ewa d E[N
=0 R(s ,a
)]. The beha io
o he agen is encoded in he policy which maps s a es o ac-
ions a =π(s ). In o de o ank he possible ac ions a one
s a e, we can compu e he Q- unc ion which ep esen s he
quali y o aking a ce ain ac ion conside ing he u u e e-
wa d. The op imal Q- unc ion Q∗can be compu ed by doing
ull backups o u u e ewa ds and ac ions ecu si ely. Then,
we can ob ain he op imal g eedy unc ion by:
π∗(s ) = a g max
aQ∗(s ,a
)(1)
In he POMDP se ing, he agen does no ha e ull ob-
se abili y o he s a e and mus ely on pa ial obse a-
ions y ollowing an obse a ion model p(y |s ,a
). Thus,
he agen elies on belie s, which a e he dis ibu ions o e
possible s a es, gi en he known obse a ions and ac ions
b =p(s |a0: ,y
0: ). Because, he belie is a su fi-
cien s a is ic, i can be shown ha a POMDP on s a e
space, is equi alen o a MDP on belie space [Kaelbling
e al., 1996]. In his case, he ansi ion model becomes
p(b +1|a ,b
)=yp(b +1|a ,b
,y
)p(y |a ,b
)dy. Then,
he ewa d and he policy become unc ions o he belie
(b ,a
)=sb (s)R(s ,a
)ds and π(b )=sb (s)π(s )ds.
In his case, he op imal policy and Q- unc ion can also be
mapped o he belie space π∗(b ) = a g maxaQ∗(b ,a
).
2.2 Bayesian Op imiza ion
Bayesian op imiza ion is a se o op imiza ion me h-
ods [Shah ia i e al., 2016]wi h wo impo an dis inc ea-
u es: a p obabilis ic su oga e model p( ) o lea n he p op-
e ies and ea u es o he a ge unc ion ha we a e ying o
op imize and, an acquisi ion unc ion α(x, p( )) ha , based
on he su oga e model, a e he po en ial in e es o subse-
quen que ies.
Mo e o mally, BO ies o op imize a unc ion :X→R
o e some domain X⊂Rd, by ca e ully selec ing he que ies
POMDP / belie MDP Bayesian op imiza ion
S a e: s Ta ge unc ion:
Ac ion: a Nex que y: x +1
Obse a ion: y Response alue: y = (x )
Belie : b =p(s )Su oga e model: p( )
Q- unc ion: Q∗(b ,a
)Acquisi ion unc ion: α(x, p( ))
Rewa d: R(s ,a
)Imp o emen : max(0,y
+1 −ρ )
Table 1: Compa ison o POMDP and belie MPD e ms wi h espec
o he co esponding elemen s in BO
o he unc ion o educe he numbe o e alua ions o be-
o e finding he op imum x∗. A i e a ion , all p e iously ob-
se ed alues y=y1: a que ied poin s X=x1: a e used o
cons uc a p obabilis ic su oga e model p( |y1: ,x1: ). Typ-
ically, he nex que y loca ion x +1 is de e mined by g eedily
op imizing he acquisi ion unc ion in X:
x +1 = a g max
x∈X α(x,p( |y1: ,x1: )) (2)
Fo example, we can use he expec ed imp o emen (EI) as
he acquisi ion unc ion [Mockus e al., 1978]:
EI (x)=Ep(y +1 |y1: ,x1: )[max(0,y
+1 −ρ )] ,(3)
whe e ρ = max(y1,...,y
)is he incumben op imum a
ha i e a ion. EI is s ill one o he mos popula choices,
al hough he e a e mul iple al e na i es depending on he
c i e ia selec ed, such as op imism in he ace o unce -
ain y [S ini as e al., 2010], in o ma ion abou he op imum
[Hennig and Schule , 2012; He nandez-Loba o e al., 2014;
Wang and Jegelka, 2017], e c.
I has been ound ha EI migh be uns able in he fi s i -
e a ions due o he lack o in o ma ion [Jones e al., 1998;
Bull, 2011]. The e o e, he op imiza ion is ini ialized wi h p
e alua ions by sampling om low disc epancy sequences.
Su oga e Model
Mos equen ly, his akes he o m o a Gaussian p o-
cess (GP), al hough o he al e na i es ha e been p esen ed,
such as Bayesian neu al ne wo ks [He nandez-Loba o e al.,
2017]. Fo he emainde o he pape we conside a GP
wi h ze o mean and ke nel k:X×X →Ras he su o-
ga e model. The ke nel is chosen o be he Ma ´
e n ke nel
wi h smoo hness pa ame e νand hype pa ame e s θ. The
GP pos e io model gi es p edic ions a a que y poin xq
which a e no mally dis ibu ed yq∼N(μ(xq),σ2(xq)), such
ha μ(xq)=k(xq)TK−1y, and σ2(xq)=k(xq,xq)−
k(xq)TK−1k(xq)whe e k(xq)=[k(xq,xi)]xi∈Xand K=
[k(xi,xj)]xi,xj∈X+Iσ2
n.
2.3 BO as a POMDP
As can be seen, Equa ion (1) is analogous o Equa ion (2).
The POMDP amewo k, as a a ional Bayesian model, can
also be applied o BO. Table 1 summa izes he connec ions
be ween hose amewo ks. I we use EI as he acquisi-
ion unc ion, hen we assume ha he imp o emen unc ion
I= max(0,y
+1 −ρ )is he ewa d. In his case, he EI is
he op imal myopic policy o POMDP, as i maximizes he
P oceedings o he Twen y-Eigh h In e na ional Join Con e ence on A ificial In elligence (IJCAI-19)
2358
QH[W SRLQW WR VDPSOH JUHHGLO
$FTXLVLWLRQ )XQFWLRQ
6XUURJDWH 0RGHO
LQI
R
UP
D
WL
R
QQ
RW
EHLQ
J
XVH
G
Figu e 1: Example o a su oga e model (blue) on op o he a ge
unc ion ( ed). The g eedy policy selec s he maximum o he ac-
quisi ion unc ion ( ed do ), bu comple ely igno es he es o he
egions which a e almos as aluable.
expec ed ewa d one s ep ahead. Mo e in e es ingly, en opy
based acquisi ion unc ions can be in e p e ed as an ac i e
lea ning p oblem, o which he POMDP can also be applied
as a amewo k [Lopes and Mon esano, 2014].
3 S ochas ic Policies o BO
BO policies a e ypically g eedy in wo ways. Fi s , hey a e
empo ally g eedy, ha is, hey look o he maximum im-
media e ewa d, al hough some lookahead al e na i es ha e
been p oposed in he pas [Gonz´
alez e al., 2016b; Lam e al.,
2016]. Second, hey a e spa ially g eedy, ha is, hey only
selec he ac ion o nex que y ha maximizes he acquisi ion
unc ion (o Q- unc ion). Howe e , one migh wan o explo e
subop imal ac ions o ga he knowledge abou he wo ld. In
ac , Q-lea ning algo i hms may no con e ge o he solu ion
using a g eedy policy due o he lack o infini e explo a ion.
Many acquisi ion unc ions, such as hose men ioned in
Sec ion 2.2 a e al eady designed o ade-o explo a ion and
exploi a ion. Howe e , his ade-o is based on he assump-
ion ha he su oga e model is good enough o p edic bo h
he expec ed unc ion alue and i s unce ain y. In p ac ice,
e en i he model is chosen ca e ully, we s ill need o lea n
he hype pa ame e s. Thus, o he fi s ew i e a ions, he
model is inaccu a e. In e es ingly enough, heo e ical e-
sul s ely on bounding he leng h-scales o he GP ke nels
o a ificially inc ease he explo a ion, o di ec ly using -
g eedy s a egies o gua an ee nea -op imal con e gence a es
wi h unknown hype pa ame e s [Wang and de F ei as, 2014;
Bull, 2011]. Fo inaccu a e models, he acquisi ion unc ion
is s ill able o p o ide some in o ma ion, bu by g eedily se-
lec ing a single alue we a e was ing some o ha in o ma-
ion. Figu e 1 shows how he g eedy policy only ca es abou
he cen al mode o he acquisi ion unc ion, while he wo
modes on he le a e almos as in e es ing o be explo ed.
Ins ead, we p opose o use a s ochas ic policy such as he
ollowing Bol zmann policy (also known as Gibbs o so max
policy):
p(x +1 |y1: ,x1: )= eβ α(x +1,p( |y1: ,x1: ))
x∈X eβ α(x,p( |y1: ,x1: ))dx (4)
This policy defines a p obabili y dis ibu ion o he nex
que y o ac ion. Thus, he ac ual nex que y is selec ed by
sampling ha dis ibu ion x +1 ∼p(x +1 |y1: ,x1: ). This
policy allows explo a ion e en i he model is comple ely bi-
ased. Fu he mo e, i has some in e es ing p ope ies o BO
con e gence as we will discuss in Sec ion 3.1. The main e-
sul o his wo k is ha he sampling p ocess o x +1 can be
done in pa allel and ully dis ibu ed, as will be discussed
in Sec ion 3.2. This app oach can be applied o any acquisi-
ion unc ion o su oga e model ha can be ound in he li e -
a u e. Ne e heless, he heo e ical analysis and pos e io ex-
pe imen a ion ocuses on GP and EI as p e iously discussed
in Sec ion 2.2.
3.1 Theo e ical Analysis
Con e gence o BO algo i hms has been ex ensi ely s udied
in e ms o con e gence a es [Bull, 2011]o eg e bounds in
a bandi se ing [S ini as e al., 2010; Wang and de F ei as,
2014]. In his pape we a e going o ollow upon he analysis
by [Bull, 2011] o he expec ed imp o emen . We show how
he s ochas ic policy om equa ion 4 has he same a es as
he g eedy policy in he limi ing case. We also show ha
he s ochas ic policy does no need o ely on he -g eedy
s a egy o nea -op imal a es.
Le X⊂Rdbe compac wi h non-emp y in e io . Fo a
unc ion :X→R, le Eu
deno e he expec a ion when
minimizing he fixed unc ion wi h s a egy u,asucan be
andom. We assume a p io π o p( ), ollowing a Gaus-
sian p ocess wi h a Ma ´
e n ke nel wi h smoo hness pa ame e
νand leng h-scales θ, ha ing he Squa e exponen ial ke nel
as he limi ing case o ν→∞. Each ke nel Kθis associ-
a ed wi h a space o unc ions Hθ(X), i s ep oducing-ke nel
Hilbe space (RKHS).
Defini ion 1. An EI(π,β )s a egy chooses:
1. ini ial design poin s x1,...,xkindependen ly o ; and
2. u he design poin s x +1 ( ≥k)sampled om (4).
This is analogous o [Bull, 2011, De . 1], bu eplacing he
g eedy selec ion by he s ochas ic selec ion. The EI(π,β )
s a egy can also be adap ed o conside es ima ed pa ame e s
[Bull, 2011, De . 3]. No e ha , o he s ochas ic policy, he e
is no need o en o ce ha he selec ion is dense o cons an
alues o he acquisi ion unc ion.
Theo em 2. Le Xbe a fini e space. I β =ln /C and
C = maxx|maxzα(z,p( )) −α(x, p( ))|, hen (4) is a
g eedy in he limi wi h infini e explo a ion (GLIE) policy.
The e o e:
1. each poin xis que ied infini ely o en i we use he
EI(π,β )s a egy infini ely o en, and
2. in he limi , he EI(π,β )policy is g eedy wi h espec
o he acquisi ion unc ion α(·)wi h p obabili y 1.
The p oo can be ound in [Singh e al., 2000, Ap. B]
ollowing he ela ions om Table 1. In o de o gene alize
he p e ious esul o X∈Rd, we can pa i ion Xin n e-
gions o size O( 1/d). Following EI(π,β )and assuming
a la ge each egion will be sampled wi h high p obabili y,
hus, he mesh no m is small, which is he equi emen o
nea -op imal a es [Bull, 2011, Lemma 12]. In ac , wi h β1
he sampling dis ibu ion is exac ly uni o m.
P oceedings o he Twen y-Eigh h In e na ional Join Con e ence on A ificial In elligence (IJCAI-19)
2359
Theo em 3. Le EI(π,β )be he s a egy in Defini ion 1. I
ν<∞, hen o any R>0,
sup
 Hθ(X)≤R
Eu
[ (x∗
)−min ]=O(( / log )−ν/d(log )α),
wi h p obabili y 1, while i ν=∞, he s a emen holds o all
ν<∞.
The ske ch o he p oo is based on [Bull, 2011, Theo-
em 5], which uses g eedy EI o op imali y combined wi h
-g eedy o gua an ee he educed mesh no m. Following
Theo em 2, o la ge , he mesh no m will be small and
he s a egy will be g eedy wi h p obabili y 1. We encou age
he eade o ollow up he discussion in [Singh e al., 2000]
whe e i is shown ha , o ce ain alues o , he s a egy
ollowed by [Bull, 2011]is also GLIE.
3.2 Dis ibu ed BO
Now we a e eady o p esen he main con ibu ion o his
wo k. The s ochas ic policy p esen ed in Sec ion 3 allow us o
implemen BO in a ully dis ibu ed se up which can be eas-
ily deployed and scaled. Con a y o mos pa allel o ba ch
BO me hods which equi e o a cen al node o keep ack o
he que ies compu ed and deployed, ou app oach does no
need a cen alized node. All he compu a ion can be done
in each node o he dis ibu ed sys em. Fu he mo e, o op-
imal esul s, he nodes only need o b oadcas hei que ies
and obse ed alues {x ,y
}, equi ing minimal communica-
ion bandwid h. In addi ion o ha , communica ion can be
asynch onous and be e en obus o ailu es in he ne wo k,
as he o de o he que ies and obse a ions is i ele an .
Algo i hm 1 summa izes he code o be deployed in each
node o he compu ing clus e o dis ibu ed sys em. The ini-
ializa ion pa equi es sampling om a low disc epancy se-
quence. This can be easily dis ibu ed by se ing he p ecom-
pu ed sequence on a lookup able whe e each node accesses i
based on hei id. Once he ini ializa ion phase is done, each
node builds i s own su oga e model (e.g.: a GP) wi h all he
da a ha is a ailable o hem. The e is no equi emen o he
models o be synch onized o upda ed, al hough each node
beha iou will be op imal i i has access o all he obse a-
ions a ailable as soon as possible.
One ad an age o his se up is ha i can be easily scaled
by deploying new nodes using Algo i hm 1, e en hal way
h ough he op imiza ion p ocess, as seen in Figu e 2. In ha
case, he fi s ope a ion is o collec all he da a ha has been
b oadcas ed in he ne wo k ins ead o using he low disc ep-
ancy sequence. Ano he ad an age is ha we can play wi h
Algo i hm 1 BO-NODE
Inpu : Budge T, low disc epancy sequence LD.
1: Que y LD o pini ializa ion poin s based on node id.
2: B oadcas x1:p,y
1:p
3: o =p...T do
4: Collec x,y om o he nodes when a ailable.
5: Upda e su oga e model p( |x1: ,y
1: )
6: Sample x +1 wi h Equa ion (4).
7: B oadcas x +1 and y +1 = (x +1)
8: end o
A
xA
C
xC
B
xB
x , y x1: , y1:
Figu e 2: Visualiza ion o he in e ac ion be ween BO nodes. We
ha e 3 nodes: A and B, which a e al eady up and wo king; and C, a
new node ha we wan o spin up mid-op imiza ion. A and B only
need o b oadcas hei new que ies and obse a ions. C needs o
be gi en all he p e ious que ies and obse a ions up o he cu en
ins an . Then i can esume i s wo k in he same way as A and B.
he β pa ame e om equa ion (4) and deploy nodes mo e
exploi a i e β →∞o mo e explo a o y β →0,o wecan
combine di e en kinds o node configu a ions, esul ing in
an o e all beha iou analogous o pa allel empe ing [Neal,
1996].
Many pa allel BO me hods ha e been p oposed in he
pas ew yea s. The main idea o all hose me hods is
o ensu e ha he pa allel expe imen s a e well-dis ibu ed
among he sea ch space, which is p oblema ic when we use
a g eedy app oach wi hou adding new in o ma ion be ween
que ies. Thus, some au ho s include a ificially augmen ed
da a by hallucina ed obse a ions [Ginsbou ge e al., 2010;
Snoek e al., 2012]o by combining op imiza ion wi h some
deg ee o ac i e lea ning in o de maximize he knowledge
abou he a ge unc ion [Desau els e al., 2014; Con al e al.,
2013; Shah and Ghah amani, 2015]o by en o cing di e si y
h ough heu is ics [Gonz´
alez e al., 2016a].
As no ed on [Kandasamy e al., 2018], he majo i y o pa -
allel me hods a e synch onous. Recen ly, a Thompson Sam-
pling app oach [He nandez-Loba o e al., 2017; Kandasamy
e al., 2018]has been applied o achie e ully dis ibu ed BO.
To he au ho s knowledge, his is he only me hod compa able
o ou p oposed dis ibu ed BO me hod.
3.3 Sampling S a egies
Sampling om equa ion (4) is no i ial. Mos acquisi ion
unc ions a e highly mul imodal wi h many la ge a eas o low
p obabili y be ween modes. This is known o be p oblema ic
o MCMC me hods. Tempe ing me hods, such as simula ed
o pa allel empe ing [Neal, 1996]usually pe o m be e in
hese si ua ions by allowing highe empe a u es and, he e-
o e, highe mixing o pa icles, in combina ion wi h lowe
empe a u es o be e ep esen he dis ibu ion. One ad an-
age o ou dis ibu ion is ha i is al eady in Bol zmann o m,
allowing us o change he empe a u e by al e ing he β pa-
ame e . In ou case, since we ha e a a ge empe a u e ha
we wan o use o sequen ial con e gence (as seen in The-
o em 2) o o dis ibu ed explo a ion-exploi a ion (as seen
in Sec ion 3.2), we can selec he empe a u e p ofile in such
a way ha he lowe empe a u e ma ches he a ge . Al e -
na i ely, we can selec ano he p ofile and use impo ance
sampling on he a ge empe a u e. In p ac ice, we ound
P oceedings o he Twen y-Eigh h In e na ional Join Con e ence on A ificial In elligence (IJCAI-19)
2360
50 100 150
unc. e alua ions
100
101
102
103
i
nme
di
a e eg e
Bohache sky
SP-EI
SP-UCB
SP-PI
GP-PDTS
EI
50 100 150
unc. e alua ions
10−7
10−6
10−5
10−4
10−3
10−2
10−1
100
101
i
nme
di
a e eg e
B anin
SP-EI
SP-UCB
SP-PI
GP-PDTS
EI
50 100 150
unc. e alua ions
10−2
10−1
100
101
102
i
nme
di
a e eg e
Rosenb ock
SP-EI
SP-UCB
SP-PI
GP-PDTS
EI
50 100 150
unc. e alua ions
10−5
10−4
10−3
10−2
10−1
i
nme
di
a e eg e
Camelback
SP-EI
SP-UCB
SP-PI
GP-PDTS
EI
50 100 150
unc. e alua ions
0
2
4
6
8
10
12
14
16
i
nme
di
a e eg e
Ackley
SP-EI
SP-UCB
SP-PI
GP-PDTS
EI
50 100 150
unc. e alua ions
100
200
300
400
500
600
i
nme
di
a e eg e
Eggholde
SP-EI
SP-UCB
SP-PI
GP-PDTS
EI
50 100 150
unc. e alua ions
80
100
120
140
160
i
nme
di
a e eg e
Schube
SP-EI
SP-UCB
SP-PI
GP-PDTS
EI
50 100 150
unc. e alua ions
10−1
100
i
nme
di
a e eg e
Ha mann 6D
SP-EI
SP-UCB
SP-PI
GP-PDTS
EI
Figu e 3: Inmedia e eg e on benchma k unc ions wi h he s ochas ic policy in combina ion wi h EI, UCB and PI. We include PDTS o
compa ison and sequen ial EI as baseline.
ha , o small dimensional p oblems as hose ypically ound
o BO, a mix u e o Gaussians wi h di e en a iance as he
p oposal unc ion and a fixed empe a u e using Me opolis-
Has ing can be enough o ge a good dis ibu ion.
4 Discussion
Al hough he main esul o his wo k is on dis ibu ed BO,
he POMDP amewo k can in oduce new in e es ing ideas
o explo e in he con ex o BO. Fo example, mul i ask-
ing o mul ifideli y sys ems ha e a g ea po en ial o high-
h oughpu compu ing wi h BO, whe e we a e able o imp o e
he con e gence o ou me hod by in oducing new in o ma-
ion om o he sou ces, ei he om ela ed p oblems whe e
we al eady ha e p e ious expe imen s o om less expen-
si e sou ces like a smalle aining da ase s, incomple e ex-
ecu ions o a simple simula o . In bo h scena ios he a ge
unc ion now belongs o a amily o unc ions om o he
asks o fideli ies k. In he bandi se up, his is equi alen o
con ex ual bandi s. In he POMDP o mula ion, he unc ion
is analogous o he s a e s(see Table 1). The POMDP model
includes a ansi ion unc ion p(s +1 |a ,s
), which can be
known a p io i o lea ned, ha defines a p obabili y dis i-
bu ion o ansi ions be ween s a es. This ansi ion unc ion
allows mo e flexibili y han con ex ual a iables.
Recen esul s on lookahead policies y o a oid he em-
po al g eediness o BO. One in e es ing app oach is based
on dynamic p og amming [Lam e al., 2016]. Howe e , as
poin ed ou by he au ho s, he dynamic p og amming ap-
p oach is challenging due o he nes ed maximiza ions and
expec a ions, equi ing heu is ics o elax he maximiza ion
s eps. By using he s ochas ic policy om equa ion (4), we
can p o ide a ull Bayesian ea men o he dynamic p o-
g amming, simila o alue i e a ion [Kaelbling e al., 1996].
5 Resul s
We show he pe o mance o ou s ochas ic policy o dis-
ibu ed BO wi h di e en acquisi ion unc ions: Expec ed
Imp o emen (SP-EI), P obabili y o Imp o emen (SP-PI)
and Uppe Confidence Bounds (SP-UCB). We also include
he pa allel and dis ibu ed Thompson sampling (PDTS)
[He nandez-Loba o e al., 2017]as an al e na i e dis ibu ed
me hod and he sequen ial expec ed imp o emen (EI) as a
baseline. No e ha [He nandez-Loba o e al., 2017]al eady
compa es PDTS wi h pa allel EI and -g eedy me hods. In
o de o simpli y he compa ison, we use a GP as he su o-
ga e model o all he algo i hms. Howe e , bo h PDTS and
ou s ochas ic policy me hods allow o he su oga e models
such as Bayesian neu al ne wo ks. In all he expe imen s, we
assume a ne wo k o 10 nodes synch onized, ha is, unc-
ion e alua ions a e pe o med in ba ches o 10 o all dis-
ibu ed me hods. No e ha EI has an un ai ad an age, as
i has access o all he da a o each i e a ion while he dis-
ibu ed me hods only upda e hei GP model once e e y 10
obse a ions. Fo all he plo s, we display he a e age o each
me hod o e 10 ials wi h a 95% confidence in e al. We use
common andom numbe s o educe he a iance in he com-
pa ison and use he same ini ial samples among all me hods.
5.1 Benchma k Func ions
Fi s , we s a wi h a se o es p oblems o global op imiza-
ion1. We ha e selec ed he unc ions o ha e a mix u e o be-
ha iou s (smoo h/sha p, single/mul iple minima, e c.). The
esul s on hese unc ions a e showcased in Figu e 3. Fi s ,
we can see how he pe o mance o SP-EI is ai ly consis en
among he di e en unc ions, achie ing be e o simila e-
sul s han he al e na i es. E en o unc ions ha a e di ficul
1F om: h ps://www.s u.ca/∼ssu jano/op imiza ion.h ml
P oceedings o he Twen y-Eigh h In e na ional Join Con e ence on A ificial In elligence (IJCAI-19)
2361

50 100 150
unc. e alua ions
10−6
10−5
10−4
10−3
10−2
10−1
i
nme
di
a e eg e
GP Sample Ma e n
SP-EI
SP-UCB
SP-PI
GP-PDTS
50 100 150
unc. e alua ions
10−6
10−5
10−4
10−3
10−2
10−1
100
i
nme
di
a e eg e
GP Sample RQ
SP-EI
SP-UCB
SP-PI
GP-PDTS
Figu e 4: Op imizing andom unc ions om a GP. A Ma ´
e n ke nel
(le ) and a ional quad a ic ke nel ( igh ) a e used in he GP. As
a Ma ´
e n ke nel is used in op imiza ion, we ha e a wi hin-model
(le ) and ou -o -model ( igh ) expe imen . I is impo an o no e ha
di e en ke nels can gene a e di e en possible andom unc ions,
making he e ical axis no compa able be ween bo h p oblems.
o op imize wi h BO, such as Schube , he s ochas ic policy
is able o pe o m well hanks o he ex a explo a ion induced
by he sampling p ocess. Howe e , his explo a ion does no
in e e e wi h easie unc ions whe e exploi a ion is mo e im-
po an , such as B anin o Bohache sky. In e es ingly, SP-PI
pe o ms easonably well. In he case o PI, he s ochas ic
policy p e en s excessi e exploi a ion, a known beha iou o
PI in he sequen ial BO se ing [Shah ia i e al., 2016].
We ha e also ollowed he me hodology om [Hennig and
Schule , 2012]and gene a ed andom unc ions om a known
GP. We ha e s udied wo si ua ions: a) we ha e s udied he
wi hin-model p oblem, whe e he GP sample uses he same
ke nel as he op imiza ion algo i hm (Ma ´
e n wi h ν=5/2)
and, b) he ou -o -model p oblem whe e he GP sample is gen-
e a ed wi h a di e en ke nel (a Ra ional Quad a ic). The e-
sul s in Figu e 4 show how SP-EI is compa able o PDTS bo h
o he wi hin-model and he ou -o -model p oblems.
5.2 Robo Pushing
In he nex expe imen , we use he ac i e lea ning o obo
pushing se up and code om [Wang and Jegelka, 2017].I
consis s o pe o ming ac i e policy sea ch on he ask o se-
lec ing a pushing ac ion o an objec owa ds a designa ed
goal loca ion. The unc ion has a 3-dimensional inpu : he
obo loca ion ( x,
y)and he pushing du a ion .Ina
second expe imen , we add he obo angle θ o ha e a 4-
dimensional e sion. In his expe imen , he epe i ions a e
inc eased o 40, as each epe i ion is a di e en goal loca ion.
Figu e 5 shows he esul s o bo h p oblems in which we can
see how ou me hods SP-EI and SP-PI ha e as e con e -
gence han GP-PDTS.
5.3 Hype pa ame e Tuning o Neu al Ne wo ks
Finally, we use he se o p oblems o hype pa ame e uning
o neu al ne wo ks om [Ma inez-Can in e al., 2018],as
hese a e good examples o he ad an age o dis ibu ed BO
o aining expensi e models in he cloud. We can see he
esul s o bo h ne wo ks in Figu e 6, whe e SP-EI and SP-PI
consis enly ou pe o m PDTS.
Va ia ional Au oencode (VAE) on MNIST. A VAE is a
gene a i e me hod ha lea ns a low dimensional ep esen a-
50 100 150
unc. e alua ions
0.2
0.4
0.6
0.8
1.0
1.2
1.4
b
es
unc
i
on a
l
ue
Robo push3
SP-EI
SP-UCB
SP-PI
GP-PDTS
50 100 150
unc. e alua ions
0.4
0.6
0.8
1.0
1.2
1.4
b
es
unc
i
on a
l
ue
Robo push4
SP-EI
SP-UCB
SP-PI
GP-PDTS
Figu e 5: Robo pushing policy esul s, showing he 3-dimensional
(le ) and he 4-dimensional ( igh ) p oblems.
50 100 150
unc. e alua ions
152.5
155.0
157.5
160.0
162.5
165.0
167.5
170.0
b
es
unc
i
on a
l
ue
VAE
SP-EI
SP-UCB
SP-PI
GP-PDTS
50 100 150
unc. e alua ions
31
32
33
34
35
b
es
unc
i
on a
l
ue
Feed Fo wa d Ne wo k
SP-EI
SP-UCB
SP-PI
GP-PDTS
Figu e 6: Hype pa ame e uning o neu al ne wo k p oblems. A
Va ia ional Au oencode ained wi h he MNIST da ase (le ) and
a Feed o wa d ne wo k ained wi h he Bos on housing da ase
( igh ).
ion o high dimensional da a, such as images. We ain a
VAE o he MNIST da ase , and une he ollowing hype pa-
ame e s: numbe o nodes in he hidden laye , lea ning a e,
lea ning a e decay and cons an o he ADAM op imize .
Feed o wa d Ne wo k on Bos on Housing. We fi a sin-
gle laye eed o wa d ne wo k on he Bos on housing da ase .
The hype pa ame e s uned a e: numbe o nodes in he hid-
den laye , lea ning a e, lea ning a e decay and ρpa ame e
o he exponen ial decay a e om RMSp op.
6 Conclusion
We ha e in oduced se e al implica ions and ad an ages o
iewing Bayesian op imiza ion as a Ma ko decision p ocess.
We also ha e shown ha his app oach can be in e es ing o
u he de elopmen s o BO, bo h in heo y and p ac ice. As
he main con ibu ion o he pape , we ha e p esen ed a new
me hod o ully dis ibu ed BO based on s ochas ic policies
which can be easily in eg a ed in any se up, independen o
he su oga e model o acquisi ion unc ion o choice. This
dis ibu ed BO allows high scalabili y, e en by adding new e-
sou ces on demand and educing he communica ion be ween
nodes. We show how, in mos cases, he s ochas ic policy ou -
pe o ms he s a e o he a on dis ibu ed BO (PDTS) and
e en o he sequen ial expec ed imp o emen .
Acknowledgmen s
This wo k has been pa ly suppo ed by p ojec s DPI2015-
65962-R, RTI2018-096903-B-I00 and DGA T45-17R.
P oceedings o he Twen y-Eigh h In e na ional Join Con e ence on A ificial In elligence (IJCAI-19)
2362
Re e ences
[Bull, 2011]A.D. Bull. Con e gence a es o e ficien global
op imiza ion algo i hms. JMLR, 12:2879–2904, 2011.
[Con al e al., 2013]E. Con al, D. Bu oni, A. Robicque ,
and N. Vaya is. Pa allel Gaussian p ocess op imiza ion
wi h uppe confidence bound and pu e explo a ion. In
ECMLKDD, pages 225–240. Sp inge , 2013.
[Desau els e al., 2014]T. Desau els, A. K ause, and J.W.
Bu dick. Pa allelizing explo a ion-exploi a ion ade-
o s in gaussian p ocess bandi op imiza ion. JMLR,
15(1):3873–3923, 2014.
[Fo es e e al., 2006]A. Fo es e , N. B esslo , and
A. Keane. Op imiza ion using su oga e models and
pa ially con e ged compu a ional fluid dynamics simu-
la ions. P oceedings o he Royal Socie y o London A,
462(2071):2177–2204, 2006.
[Ginsbou ge e al., 2010]D. Ginsbou ge , R. Le Riche, and
L. Ca a o. K iging is well-sui ed o pa allelize op imiza-
ion. In Compu a ional in elligence in expensi e op imiza-
ion p oblems, pages 131–162. Sp inge , 2010.
[Gonz´
alez e al., 2016a]J. Gonz´
alez, Z. Dai, P. Hennig, and
N. Law ence. Ba ch bayesian op imiza ion ia local pe-
naliza ion. In AISTATS, pages 648–657, 2016.
[Gonz´
alez e al., 2016b]J. Gonz´
alez, M. Osbo ne, and
N. Law ence. Glasses: Relie ing he myopia o bayesian
op imisa ion. In AISTATS, pages 790–799, 2016.
[Hennig and Schule , 2012]P. Hennig and C.J. Schule . En-
opy sea ch o in o ma ion e ficien global op imiza ion.
JMLR, 13:1809–1837, 2012.
[He nandez-Loba o e al., 2014]J.M. He nandez-Loba o,
M.W. Ho man, and Z. Ghah amani. P edic i e en opy
sea ch o e ficien global op imiza ion o black-box
unc ions. In NIPS, pages 918–926, 2014.
[He nandez-Loba o e al., 2017]J.M. He nandez-Loba o,
J. Requeima, E.O. Pyze -Knapp, and A. Aspu u-Guzik.
Pa allel and dis ibu ed hompson sampling o la ge-scale
accele a ed explo a ion o chemical space. In ICML,
pages 1470–1479, 2017.
[Jones e al., 1998]D.R. Jones, M. Schonlau, and W.J.
Welch. E ficien global op imiza ion o expensi e black-
box unc ions. J Glob Op im, 13(4):455–492, 1998.
[Kaelbling e al., 1996]L.P. Kaelbling, M.L. Li man, and
A.W. Moo e. Rein o cemen lea ning: A su ey. JMLR,
4:237–285, 1996.
[Kandasamy e al., 2018]K. Kandasamy, A. K ishnamu hy,
J. Schneide , and B. Poczos. Pa allelised Bayesian op imi-
sa ion ia hompson sampling. In AISTATS, 2018.
[Klein e al., 2017]A. Klein, S. Falkne , S. Ba els, P. Hen-
nig, and F. Hu e . Fas Bayesian op imiza ion o machine
lea ning hype pa ame e s on la ge da ase s. In AISTATS,
2017.
[Lam e al., 2016]R. Lam, K. Willcox, and D.H. Wolpe .
Bayesian op imiza ion wi h a fini e budge : An app ox-
ima e dynamic p og amming app oach. In NIPS, pages
883–891, 2016.
[Lopes and Mon esano, 2014]M. Lopes and L. Mon esano.
Ac i e lea ning o au onomous in elligen agen s: Explo-
a ion, cu iosi y, and in e ac ion. a Xi :1403.1497, 2014.
[Ma inez-Can in e al., 2018]R. Ma inez-Can in, K. Tee,
and M. McCou . P ac ical bayesian op imiza ion in he
p esence o ou lie s. In AISTATS, pages 1722–1731, 2018.
[Ma inez-Can in, 2019]R. Ma inez-Can in. Funneled
Bayesian op imiza ion o design, uning and con ol o
au onomous sys ems. IEEE T ans Cybe n, 49(4):1489–
1500, 2019.
[Me ino-Casallo and o he s, 2018]F. Me ino-Casallo e al.
In eg a ion o in i o and in silico models using Bayesian
op imiza ion wi h an applica ion o s ochas ic modeling o
mesenchymal 3d cell mig a ion. F on . Psychol., 9, 2018.
[Mockus e al., 1978]J. Mockus, V. Tiesis, and A. Zilinskas.
The applica ion o Bayesian me hods o seeking he ex-
emum. In Towa ds Global Op imisa ion 2, pages 117–
129. Else ie , 1978.
[Neal, 1996]R.M. Neal. Sampling om mul imodal dis i-
bu ions using empe ed ansi ions. S a is ics and compu -
ing, 6(4):353–366, 1996.
[Sacks e al., 1989]J. Sacks, W.J. Welch, T.J. Mi chell, and
H.P. Wynn. Design and analysis o compu e expe imen s.
S a is ical Science, 4(4):409–423, 1989.
[Shah and Ghah amani, 2015]A. Shah and Z. Ghah amani.
Pa allel p edic i e en opy sea ch o ba ch global op i-
miza ion o expensi e objec i e unc ions. In NIPS, 2015.
[Shah ia i e al., 2016]B. Shah ia i, K. Swe sky, Z. Wang,
R.P. Adams, and N. de F ei as. Taking he human ou o
he loop: A e iew o Bayesian op imiza ion. P oceedings
o he IEEE, 104(1):148–175, 2016.
[Singh e al., 2000]S. Singh, T. Jaakkola, M.L. Li man, and
C. Szepes ´
a i. Con e gence esul s o single-s ep on-
policy ein o cemen -lea ning algo i hms. Machine lea n-
ing, 38(3):287–308, 2000.
[Snoek e al., 2012]J. Snoek, H. La ochelle, and R. Adams.
P ac ical Bayesian op imiza ion o machine lea ning algo-
i hms. In NIPS, pages 2960–2968, 2012.
[S ini as e al., 2010]N. S ini as, A. K ause, S. Kakade, and
M. Seege . Gaussian p ocess op imiza ion in he bandi
se ing: No eg e and expe imen al design. In ICML,
2010.
[Toussain , 2014]M. Toussain . The Bayesian sea ch game.
In Theo y and P incipled Me hods o Designing Me a-
heu is ics. Sp inge , 2014.
[Wang and de F ei as, 2014]Z. Wang and N. de F ei as.
Theo e ical analysis o Bayesian op imisa ion wi h un-
known Gaussian p ocess hype pa ame e s. a Xi , 2014.
[Wang and Jegelka, 2017]Z. Wang and S. Jegelka. Max-
alue en opy sea ch o e ficien Bayesian op imiza ion.
In ICML, olume 70, pages 3627–3635, 2017.
P oceedings o he Twen y-Eigh h In e na ional Join Con e ence on A ificial In elligence (IJCAI-19)
2363