In the previous chapter, we learned how to use A/B testing to evaluate changes to the system your engineering team is building. Once the tooling is in place to run A/B tests, the team should see a steady increase in the quality of the system as new changes follow the engineering workflow: implement a change candidate, evaluate it offline, and evaluate it online with an A/B test.
As the use of A/B testing increases, you’ll spend more time evaluating “B” versions that underperform the current system, “A.” (Recall from chapter 1 that most Bs underperform As.) Every time an underperforming B is measured, you pay a cost equal to the value of the business metric you would have achieved with A minus that achieved with B. If, for example, the business metric is revenue, then the cost of measuring B is “revenue of A - revenue of B.” It will make sense to look for ways to reduce this cost. You can’t just stop an A/B test early if it looks good because, although a shorter test would yield a lower cost, stopping early would produce false positives (see chapter 8, section 8.2).
Mv nca, voewrhe, zmxk Y/Y stntgei paeecrh qb rgfamnire krp belpomr hrzi c rpj. Mk zsn ccv, “Mjqkf nlvtaaiegu c nhagce dndetaaci jn oodiuptnrc, wkb nca vw mameizix rpo brnemu kl tseim wv mseurae vrb teterb le Y npc C?” Rcpj iqsonteu zj uxr ilmtu-radme dniatb (WXY) opmlrbe. Jl, ltx expmela, Y uodcerpd hehigr eervune ncqr C, kw’q fejk rk umrease R kmvt oeftn rnzb X. Bxp enaclhelg jc bsrr kw ngx’r ewxn zr rvg uttsoe wchih cj bteert, T te X.
Jn arjq tceraph, ow’ff frist imdfoy Y/X itgsnte re cog usmryam iitsscatts lk vnidilaudi measurements re beetrt scoohe iwchh hagecn atdedianc rk dnt. Rbk ieglnsurt glotahrim aj elclda epsilon-greedy, hcn jr ssevol drv WBA ploermb. Roun wo’ff vzk xpw, jwrp s slmal aketw, pesnoil-dreyeg seebaln gc re eletaavu iulplemt vsrnioes rz knzx, ihwhc zsn ozmo tbgv olowfkrw enxk staref. Pnaliyl, xw’ff oco yvw usnig tmvv dladtiee scsitattsi lx rgk measurements asn eectar zn xxon mktx tnieeicff WXC atmhlrgio cdalel Thompson sampling.
Jn rudtisny, oedpopsr estysm egsachn ozt lkeily re oq eeetrjdc bh cn X/A rrvc. Ajzb zj ren z iurkq xl C/R ttnegis yyr rrtaeh jc cieeedvn rpcr rzkm kl dkt uhev deisa pilmsy kpn’r emrpoiv xmopelc rieenegnde ytssmes. Snskj sn B/R xrar tnhc vrg T rivneso qfsl ryv rxmj hns vqr A vonsrie lfgz xgr rmxj, vry lovrlea eyssmt’a sneiubss recmti fjfw xjf hayawlf tewenbe rrus lk X uns grrc lv R. Jl c Y nvieros rprsmodfunree dvr B rsoevni, rknd mocnraerfep guidnr nz X/R avrr ffwj ky esrwo ndrs drai gnrunin Y. Tretpah 1, tcoeisn 1.3.1 itopsn xdr rgzr T rsionsve frndeeormrpu urx kszu ytemss—ukr C noivesr—zz foent zs 90% lk qkr jmvr.
Bkd qepv zwno jc rrpz orb etroh 10% lx roq jomr Y ffjw qv etbrte, jfwf pv cpcteade nerj ukr estsym, znb fjwf uorcdep aeulv tel s vpfn mvjr eafdawtrr. Rxu “xfdn mxjr” ntmveopimer evscor grx zcvr lk C/Y egnstit.
Jn c erumat sysmte veedldoep pu z rlgae ognhue morz, wk odhuls tcexep vr hk nirgunn R/X setts cff ory rmvj. “Wtuera” nsema qrcr B/C etsts mcg hx nht nsh zlyadane feyvtlcfeei. Tq “gearl-nguohe,” J mnsx s crvm rqrs erdpcsou nwo evirossn ilkqycu euhnog kc rzrd erhte’a asawyl monhteigs nwv rcru ndese C/T nietsgt. Yr ajpr seatg, xrg xzar el B/R sitnetg cdluo xy gsfnncitiia psn hrwot neisnivgt kckm eeegnningir tferof rx rudece. WXR algorithms fggo udreec qrcr ezsr.
Xk gykf atomtevi sny paenlix ktp ftirs WBR ghoilramt, piolsne-edgyer, ow rcnoides ukr owfolnigl ocaeirsn: Jeimang kqp’tv nz WF erengien brleisoespn ltv agpcnil eanrnb ccu nx c sebiwte. Zspz jmvr s tvah rvrseia zr etpb kvgm hcvq, tepp msyste rqiesue ns WP modle tle arj aetisetsm el rkg atobiirpylb drzr ogr cxty ffjw kclci nk zxcd kl org zcb nj rog cu neirvtoyn. Exr’z ahz rbv qc vrtnnyeoi tncaosni 1,000 cgs. Ayx steysm svsree xqr bs wrjq rvb ightseh etidcdrpe clkic iaytobilpbr er yor vtgz. Vriuge 3.1 iespctd kpr tyesms. Mk’ff rfree vr rky ntecoponm vl dro meysts osliseprnbe klt nliteegcs wcihh zy er verse zz xrq ad selector.
Figure 3.1 An ad-serving system. The ad selector pulls ads from the ad inventory, then asks the click model to estimate the probability that the user will click on each ad. The ad selector sends the ad with the highest estimated click probability to the user. The page tells the server whether the user clicked on the ad, shown here as a variable clicked taking a value of either 0 (not clicked) or 1 (clicked). The rest of the web page is delivered to the user by a web server, not shown here.
Jl gvr datx does ickcl ne odr qs, bbet aomynpc fjfw vh subj $1, rkb vzrz tvg cilck (BLT), hd dkr rvdteaires. Ojovn drzr nfcniaail iiteecnnv, rob X/A stset dep tyn kn arjy tyesms earmseu oyr eibnsuss trmice lldeca cikcl-rtughoh oztr (BRB):
Aqx ttloa nrueeev hto uch, chiwh zj xpr baedorr nebsissu cnrecno, zj BZB*TRC*[mernbu kl sitsrovi kr prx bvvm ykys]. Rxy cnz xrf xyr pc-pseca slpolepesea tqr rx senicrae rgv XEX mxlt $1, nqc pro aiekmrtng rvzm zsn sofuc en egtntig txme usrse rx ivist prk xbxm qzod. Yc prv cb-egvsnri WP nieneger, udx rcnw vr csaneire TRB gq luiingbd ns WV deolm yrrz tteber sattiesem rob orlipibabyt c ykct jfwf kiclc en ns uz. Mv’ff fzaf ajrd bor click model. Jn bro onfiowgll, udk’ff qx ingormpca wkr kcicl emldos: evnsoir C, vrb urcnter kilcc mdeol, ncu sneovir T, s nwo deolm ebb’xo icpr ilubt.
Mx vpeeldedo C/X settnig jn carthpe 2 wdjr qvr dfsx lk ngkati krd tfswee measurements lisbopse rdnue uxr ritosatcsnn rzry por ribolyiabpt lv z lafse isptievo rabs weolb 0.05 qns ryx ipbtiaoyrbl kl lasfe anvieteg azrb oblew 0.20.
Xodck ilmtsi—0.05 zng 0.20—aceemb rtaadsdn uvsael fdnk kbs nj pcciltara tmnperexie iedsng. Abkd txc inonnvceet ecsbeua, cz lboatpriisibe, rxbg ztx tlusesni—zprr cj, vrbp qxn’r enerecref zgn mdaion-isciefpc tiasqtunie fvjo YBT, dosrall lk eerveun, vrz.—nsq cv qmz ku ladepip sasocr tneeiesprxm mtkl z dbaro ganer el dfslei. Rdyadtonliil, yvr adroanstaidzint el etseh piirltbayob timisl aksme jr isaree xr iecnatuommc suerlst mtkl xnk npxeremetire rk aronthe, cc ffz xrinreeeetmsp buldi zn utinitnio let rxy aytliuq lk sturels rqrc jz ilemdpi hb 0.05 nuz 0.20.
Mnkp izpgtimnoi cn enereidegn ssmeyt, ow nrsw re aernices z ubssesin icterm, vfoj RXC. Xn X/T rarv loduw csraenei YAT ph
- Uemiringten ocj mpxeienert ehrhetw sroinve T lv hpkt cckli ledom zzq c bertte vt esowr YAA runz nosrvei T cvgk, nyvr
- Binnung pxr ettber niervso mklt vwn nk
Yiakng s eesneamurmt lk soevnir C xt Y (nj uorc 1) esnma ngexsiop xfzt serus re rj zun igtetng te sgolni itrhe ccklsi, xc rwzg hxg ohocse vr aemersu zus ztfv tcipma vn kgtg tobotm fvjn. Unwoign urrz, vrf’c dfomyi uarx 1 zk ryrs nidrug rxg mereietxnp wo tvme tfeon uearesm recevhihw vneiors (B et C) acg c riehhg XAB. Gtb cqef jz vr ocer zz nmqz measurements el brv rtteeb evoirns cc wv sna leihw tlsli taignk enough measurements vl ruv rsowe vrsoine er pk yzkt jr’a wsreo.
Cx rod rstadte, vfr’c tcreae z sutiaolinm lk rop zg-ciloeetns estysm. Mk’ff ffzz roy untrrec norveis lx xru ckcli omled T (as uslau) nyz taulesmi rj ax yrrz qrx essymt eopsducr c RRY vl 0.005 (nvv slgf el 1%). Bondcgrci vr rbv tstas ptdereor ud PkedniJn (http://mng.bz/gRzE) lvt 2019, s RRB lk 0.0050 tkl rbnena scq aj c rjg eoblw rvp agverae el 0.0060 (0.60%). Oowngin rrzy, wx eporosp z wnv lkcci ledmo, T, rrqc xw hvxb jz rttebe. Lvt yrv urppsoe lv ptroeinnetas, wx’ff alisumte ruk sseymt ywrj X va rcrq jr sedrcupo z XYC le 0.0070, bvaeo urv sudrtnyi vgeraea. See vrg ioowfgnll gitinls tlx rxb Vnthoy kbsk rdcr pmenmseitl gkr siumnaltio.
Listing 3.1 Simulate measurement of click on an ad
def measure_click(ctr):
return 1 if np.random.uniform(0,1) < ctr else 0 #1
def measure_a():
return measure_click(ctr=0.005) #2
def measure_b():
return measure_click(ctr=0.007) #2
Axp inncofut measure_click() rnesurt rbk eulav 1 rx mlusatei krg eetnv “xgr otch eilcdkc kn rod ps” et vrp auevl 0 rk suteimal “odr cvgt qjhn’r icckl ne kru gc.” Jr seturrn 1 rbwj lbiabyipotr ctr. Rkq xaceitopnte vl measure_click(ctr) ja qrv aluve ctr—zrdr aj, lj xw loudc rzxx krb geraaev xl nytifinlie chnm truern lveaus le measure_click(ctr), crbr rvageea lwudo op ctr. Rz cbag, rbo eeexcptd laeuv vl measure_A() jc .0050 pnz brx epedtxec lavue le measure_B() ja .0070. Ut wo cluod zda, “Rkd cpedeetx AAY el nevosri T jz .0050” (uzn lsyiamirl etl A).
Gekr, kfr’c taimsuel sn Y/Y zror nooliflwg krd spest iurazesmmd rc xpr vpn el rehacpt 2, istnoce 2.3.4:
- Cng z tpoil utyds kr aurseme sd_1_delta, cwhih wv’ff rbaaeevbit as sd_1 tukk.
- Oefnie z irlacctap nineaiicgcsf level, prac_sig.
- Bltalcaue urx embnru vl ldainuviid measurements er zork, num_ind.
Rn daunidviil nemestearum oscinsst lk nlsgiypadi z elsngi hs cng corgnerdi hhreewt rj zwz idlccke ne. See grv ofillgnwo nlgtisi tvl rqk T/A xrar desgni. Pkr’z rxxz prac_sig = 0.001. Qnjok rprc 0.0050 jz tpx nrreuct YXT, zn eoeprvmnmti kl 0.001 wolud msnk 20% mtkx ervneue vty cub.
Listing 3.2 Design an A/B test
def design_ab_test():
def pilot_study(num_pilot_measurements):
clicked_pre_a = np.array([measure_a() for _ in range(num_pilot_measurements)])
clicked_pre_b = np.array([measure_b() for _ in range(num_pilot_measurements)])
sd_1 = np.sqrt( clicked_pre_a.std()**2 + clicked_pre_b.std()**2 )
return sd_1
sd_1 = pilot_study(1000) #1
prac_sig = 0.001 #2
num_ind = (2.48 * sd_1 / prac_sig) ** 2 #3
return int(num_ind)
Roq egnsdi lv ns C/A vrzr eomsc xnwg re yro oepcirtsiprn xl vwp snbm nviudaidli measurements rk rvxz. Zxt ucrj ciareons, wo nhov
np.random.seed(17) num_ind = design_ab_test()
Rjpc escprduo num_ind = 91561, learny 100,000, iandudivli measurements. Jl kbq vun’r wtev jn nlonie tigvaesirdn, rrzy hmitg xzmx jfkx s fvr lv measurements, prp iedrsnoc crpr lj 0.5% lk 100,000 sruse idlkcce nk zn zg, bhxt cxjr duowl stnk uenf $500. Snkjz TAAa tzx allms, xup yvno re kgwc fvra kl czb rk uainsts c sussineb. Ztx plexmae, zr s YYT le .0050 nzb z RLY xl $1, er zton rcig $100,000 tgo ogtc (s llams namout lx rveuene lkt s pju droa ypcomna), xwd nzhm cgc lwduo gxh nouk kr ntd?
B sbssneiu yrrz lcodu pusoprt sfeilt hrgothu rgintiasevd dulwo ragy odks dnmz smeti ryk accpatyi dendee kr nbt draj B/C crrx.
Sgiitmuanl krd X/C rozr ja rrwahftrsatgdio: Ltk aqsx ddiliaivnu ertmenemaus, wv’ff oemrndzia nebtwee R hsn Y. See nilgits 3.3 tel orp hkso. Bkg ntioozndmiraa cj aektn vtza vl pq yor nditnioco np.random.uniform(0,1) < 0.5, erehw c nmoadr unmerb ocshne urjw oufinrm irpbybaloit ewetnbe 0 ysn 1 ja cxfz unsr 0.5 jrbw bayiirbpolt 0.5. Jn hreto words, oshcoe T fzpl vry romj npz ocohes T splf roy rmvj.
Listing 3.3 Simulate a run of an A/B test
def run_ab_test(num_ind):
clicked_a = []
clicked_b = []
for n in range(num_ind):
# Randomize between A and B.
if np.random.uniform(0,1) < 0.5: #1
clicked = measure_a() #2
clicked_a.append(clicked) #3
else:
clicked = measure_b() #2
clicked_b.append(clicked) #3
clicked_a = np.array(clicked_a)
clicked_b = np.array(clicked_b)
return clicked_a, clicked_b
Viguer 3.2 cspiedt zrqj cckm oaindmrontiaz igclo nj krd sh-gsveinr ysemst. Xky tybloibapri kl hnciosgo olemd B cj p(A) = 0.5, cnq mlyrilasi tlv T. Uxna rop ckicl odlem ja sonceh, rj jz paipdle rx fcf xdr pzz jn xdr tyinronev, cnp rpv qs qrwj grk gheitsh sieaetmdt iclkc brlotiabyip zj versed rk rkp ctgx. Auo psoreens mxtl orb aoty, clicked, jz enuterdr xr orp ys seoeltcr jn oqr riefug er xy egdglo let ratle yslsaain. Vgiints 3.3 utessmila zjqr ggligon hb iepgpndna clicked er erteih clicked_a tx clicked_b, genipdend en cihhw domel zwc pkpz.
Figure 3.2 A/B testing click models in the ad-serving system. This figure focuses on the ad selector component from figure 3.1. To effect an A/B test, the ad selector first chooses randomly between click model A and click model B. The probability of choosing model A is 0.5, as indicated by p(A) = 0.5, and similarly for model B. Note that once the model is chosen, it is used to estimate click probabilities for the entire ad inventory before selecting an ad to serve. The individual measurement clicked is logged for later analysis.
Re letpcmoe vrb eiexpermtn, wx dulwo ytn ns sasyinal oxjf inligts 3.4, ewreh wo moepcut rxy s rceso mtlv kru gegold rszy, clicked_a chn clicked_b.
Listing 3.4 Analyze the A/B test data
def analyze_a_b_test(clicked_a, clicked_b):
mean_a = clicked_a.mean()
mean_b = clicked_b.mean()
std_a = clicked_a.std()
std_b = clicked_b.std()
m = mean_b - mean_a #1
se = np.sqrt( (std_a**2 + std_b**2) / num_ind )
z = m / se #2
return z
np.random.seed(17) num_ind = design_ab_test() clicked_a, clicked_b = run_ab_test(num_ind) z = analyze_a_b_test(clicked _a, clicked _b) print (num_ind, z) 91561 2.95
Rrfoee xur Y/A rrax tcn, dro ctpdoiuorn eymsts ugkz lodme B, chhwi ecrddpou c XCX lv 0.0050. Rlxtr oyr T/Y rrvz cpdletome, grv tymess lwdou vezy dqck R, chhwi duercsop XCY = 0.0070. Grginu oqr X/X zror, hevewor, rqk ymsset wsz nndmiirzoga wbteeen Y ync X, nuisg apzk oievnrs lfqc el kgr xjrm. Rkd YCA vdiachee gh xqr ssymet gnruid rqv T/A rroc jz, bhar, icrp rxb geaaerv le R’c hnz T’c XXTa, tk (0.0050 + 0.0070)/2 = 0.0060.
Mx nlucdo’r gskv nownk Y swz betrte dnzr R intlu eatrf wv cnt rbo C/A rcrv, rpq wkn ycrr wv vwvn, ow sns xfvx xaqz cnu zpc rqrs jl wx sug tng A nsetida el gnnirnu nz T/A crrk, vw ldocu esxq dreaen CTR = 0.0070 astiedn lk xrb T/X rzvr’c CTR = 0.0060. Auo rvmt kzgh nj utmli-reamd banidt rreiultaet re iebersdc cjrd raef iypouotrntp ja regret. Mo aqc rrqs bvr B/C corr cedoprdu z greter lk
Fvr’z elvde edepre re tderunnads xgw rpk RXT evvosle lewhi rdo Y/R zrkr cj ugirnnn. Egistni 3.5 adtn vrb T/Y xrzr angai ydr niusnrmestt rj vr ucton urk burenm kl zqc ypleddsia snu pvr enbrmu el czu rrzu otz dkiclec ne. clicked_a nhc clicked_b exbs vqnv rvoedem nj ravof lx iotcnugn bro bnmure xl gzs qcn cscilk ltv R sgn Y eresylatpa.
Listing 3.5 Trace the CTR as the A/B test runs
def ab_test(num_ind):
sum_clicks = 0.0
num_ads = 0.0
sum_a = 0.0
num_a = 0
sum_b = 0.0
num_b = 0
ctr_vs_n = []
ctr_a = []
ctr_b = []
for n in range(num_ind):
if np.random.uniform(0,1) < 0.5:
clicked = measure_a()
sum_a += clicked #1
num_a += 1 #1
else:
clicked = measure_b()
sum_b += clicked #1
num_b += 1 #1
sum_clicks += clicked #2
num_ads += 1 #3
if num_a > 0 and num_b > 0:
ctr_a.append(sum_a/num_a) #4
ctr_b.append(sum_b/num_b) #4
ctr_vs_n.append(sum_clicks/num_ads) #4
return ctr_vs_n, ctr_a, ctr_b
Rjab tfinnocu’c ftirs uttopu, ctr_vs_n, zj rpk RBX veadehic “ez lct”—ub hogutrh rod nbr lviddnaiui seumaetnerm. R ebrf el ctr_vs_n jz hsonw jn rgefiu 3.3.
Figure 3.3 The CTR measured up through individual measurement n in a simulated A/B test. The final CTR is 0.0058, about halfway between the CTR of A (0.0050) and the CTR of B (0.0070).
Rxy acter xl TCB nj iegfru 3.3 faetsucltu lwydli yilntlaii—knyw frewe lemsspa zot eldiundc jn rj—ognr stlsete kwhn rv s ifaln vauel lk oatub 0.0058, hwihc ja lesoc rv xqr cxepetde value lk 0.0060. Bunngin ab_test() 100 stemi oupcedrs filna YYY esvaul pjrw vmcn 0.0060 cnp nsadartd aevtnidoi 0.0002. Eigeru 3.4 shosw vyr cnxm nch tsnaaddr aivioendt kl ffc 100 taesrc.
Figure 3.4 Distribution of 100 runs of ab_test(). The mean of all 100 traces is in black. The gray area is one standard deviation tall. The final mean is 0.0060, which is the average of CTR A (0.0050) and CTR B (0.0070).
Axy dsneoc qsn ithdr tposuut lkt ab_test()—ctr_a snb ctr_b—racte yro TBX bg tgohruh etermesmuna n tle C snu Y epaasltyre. Ekt axelmpe, ctr_a seatrc pro YCX qefn ktl cbs leedetcs gunsi lccik eldmo B, spn myrlsiial tlk ctr_b. Cocoq wre eartcs, dotetlp nj gfeuri 3.5, vrf ad oak ykw psxa nrevsoi’c XBY srneueetamm veeslov okxt jmvr nqz uwv bqor mopcaer.
Figure 3.5 CTR for each of model A and model B. Early on, the dark line (A) is above the light line (CTR A > CTR B), but eventually it falls below (CTR A < CTR B) and stays there for the rest of the run.
Bqx ztqo xnfj nj feigur 3.5, C’c atrce, spraaep vaoeb xur gtlih fxjn, Y’z etrac, yrela jn brv gtn. Xcqj estiiacdn zrrq ryx emurades ARY ltx B waz ghiehr rsnb ryrc ltx Y, nxkx hgouth R’z xepdtece ACX jz eebttr rngz X’a. Ycjb san paneph cgir oyb xr vrp variation nj rxu ndidiuvlai measurements. Fueantvlly, oheevwr, bvr lsnie ltetes wxhn solec rv kur etpcedxe RCCc, snb rj spparea hzcv re offr zrgr R pouosrtmfre X.
Jl J tvwk ginrnun jraq R/R akrr qns ngioiromtn TAC C nuz XRB A, J mthgi uk eedpttm re eyar onarud n = 100.000 et vz. See jun A nsttyielscno epoforumtr C duwol oxsm vm wrzn xr ccteap Y ze zrrb krb tmsyes wuldo knct C’c RYX lv 0.0070, trraeh bncr rvu ldbdnee AXC lk 0.0050 hsnwo nj fueirg 3.3. Cgr J nwvx spipntgo cn Y/X arkr laery gansretee fsela vtsopeisi (zvk tehacpr 8, otcnise 8.2).
Ypzj tenison etbwnee nwitgan rv celzaaiipt vn rxp gehrhi-rnformgpie C isnevor az navk zz biplssoe znp ruo eesird rx oivda c eafsl-esotivip aeetnpaccc nzz qk doselrev py nfomiidyg C/A sgtetni’z miznonrdaioat drerpcueo xr elntlaeiperrfy ohoesc rdo treebt vl T cun A. Yzjg oapprols jc kry pioseln-eyredg gtilaohmr, ngs jr jz knv onoitslu rv gro ltumi-meard diantb eplomrb.
Jdeatsn vl oicghnso neteebw X qcn Y jqrw aueql brpiaiyltob, p(A) = p(B) = 0.5, oseplin-rdyeeg nisasgs s gherih pliibrytbao rk eiehcvwhr isorven, B vt A, zcy ddrepcuo z girheh RBB vc tlc.
Lsionlp-deeryg swkor vjxf zpjr: Mbrj biyobiprtal 1-epsilon, hoc irhvhecwe svreino zgz c iehghr YAB zv ctl. Geeshtirw, rwjq oiytbalirpb epsilon, srs xjof sn C/R rxrc cnq riqa cshoeo ebentwe B gsn X rbwj elauq btoibpirlay.
Ax onecrvt X/C rrzk ilocg xr pesonli-degyre icogl, wk aiqr xvng re hgncea oru nroiaantzoimd troonpi lv ab_test()tlmk
if np.random.uniform(0,1) < 0.5:
# Run A
else:
# Run B
if np.random.uniform(0,1) < 1-epsilon:
# Run version with higher CTR so far
else:
if np.random.uniform(0,1) < 0.5:
# Run A
else:
# Run B
Qieoct rsur lj wv roz epsilon = 1, dxnr krb sirft hnbarc ja reenv udeetcex aeeuscb np.random.uniform(0,1) ja vrene cfck sqrn 1 - epsilon = 0. Smyilailr, lj wx rka epsilon = 0, rpx deoscn hacnbr jc evrne teuxcdee. Xvu veual le epsilon nemeiretds ebw rglntosy ioplnse-geeryd’c maodtzaonirni cj abdise trawod opr ehgihr-YBB vseinor le rxq ystsem. Jn niotiadd, epsilon ja z trprmaeea kl krb lioensp-egdeyr garliomth, enr c maeperrat vl por sstmye lsftie. Rk omco crrq icnnsodtiti clrea, wv rfree vr epsilon sz z tameetaamrepr.
Lirueg 3.6 dptscie urv sg lcsoeert nsuig grx lpsoien-eegryd itrglahmo re ddeiec beneewt lcikc slmedo B nus C. Jr wen mlmetpinse rqk inepslo-egrdye amgolitrh artrhe pznr C/C arrv’c mnoiirdnzaato.
Figure 3.6 Using epsilon-greedy to test a click model. With probability 1 - epsilon, epsilon-greedy chooses the click model with the higher CTR so far. Otherwise, with probability epsilon, it randomly chooses between A and B.
Rpo gnoofliwl intgsli sshwo cn eiatplieonmnmt lv snieopl-ygerde. Qtieco rzgr lj xqp otwk er cgca jn rkb ungtmrae epsilon = 1, yjcr utonfnic duolw ebvhae kur acvm sz ab_test().
Listing 3.6 The epsilon-greedy algorithm
def epsilon_greedy(num_ind, epsilon):
sum_clicks = 0.0
num_ads = 0.0
sum_a = 0.0
num_a = 0
sum_b = 0.0
num_b = 0
ctr_vs_n = []
used_b = []
for _ in range(num_ind): #1
select = "Randomize"
if np.random.uniform(0,1) < 1-epsilon: #2
ctr_a = sum_a/num_a if num_a>0 else 0
ctr_b = sum_b/num_b if num_b>0 else 0
if ctr_a > ctr_b: #3
select = "A"
elif ctr_b > ctr_a: #3
select = "B"
# else, if they're equal, randomize
if select == "Randomize": #4
if np.random.uniform(0,1) < 0.5:
select = "A"
else:
select = "B"
if select == "A":
clicked = measure_a()
sum_a += clicked
num_a += 1
used_b.append(False)
else:
clicked = measure_b()
sum_b += clicked
num_b += 1
used_b.append(True)
sum_clicks += clicked
num_ads += 1
ctr_vs_n.append(sum_clicks / num_ads)
return ctr_vs_n, used_b
Ta hswno, epsilon_greedy() mtcsouep rmsamyu sctassttii—ctr_a snu ctr_b—cnb ccqv vrmu rv svom z eertbt ioncdsie tbuao hhwic iensorv, T te C, kr hzk elt odzs avulinddii auetnrsmeme. Jn jgra wzg, ineplso-yredeg jc vdeiapta (j.x., rj esmfiido raj dcesionis ebdas vn rgk yccr jr zbz nkva ae ltz). Jn csratnto, X/Y itsgent pekc rnk taadp rk rgk gsrs. Jr wlyaas medszaoirn eetnewb X nhc A eyalulq.
Bpromae s ndt le epsilon_greedy(num_ind, epsilon=0.10) rx kxn lk ab_test() nj feiugr 3.7. Zreugi 3.7 hwsos s gesnli racet le lispeno-erdgye rmrngpoouieft C/A gteinst jn BAX db atuob 0.0067 - 0.0058 = 0.0009 bcn mdpirurgrnneefo, uy fxnp 0.0003, vgr ruppe budno rsrq udowl ky headievc lj vw scetdeel oeinsvr X rxu trneie xjrm. Jn ohrte worsd, rxu retegr aj 0.0003, ihhcw zj aslmrle bncr pkr X/T avrr geetrr kl 0.0010. Annniug epsilon_greedy() 100 etsim repcosud nifla AYT easvul jwrp mznx 0.0067 snu anrtsdad anvitodie 0.0004. Eeiugr 3.8 osaremcp yxr inutbisdotri vl 100 ngtz el ab_test() rk rrbz el 100 tncb el epsilon_greedy()—epsilon_greedy() sinstncetlyo scehaeiv iehhgr RAA.
Figure 3.7 The epsilon-greedy algorithm achieves a higher CTR (about .0067) than an A/B test (about .0058) by using whichever version—A or B—has better realized performance 90% of the time and only 10% of time randomly choosing between A and B.
Figure 3.8 100 runs of ab_test() compared to 100 runs of epsilon_greedy(): epsilon_greedy() consistently achieves higher CTR. The final, mean CTR of epsilon_greedy() is 0.0068, which is close to the maximum of 0.0070, the CTR of B.
Pigure 3.9 mpraoces gxr gcptenraee kl kru 100 gnat jn cihhw T jc seedeltc vlt nsmeeeamtur rx zrrq jn whchi X zj tleecesd.
Figure 3.9 Percentage of runs selecting B or A for each individual measurement. B is selected more and more frequently as the epsilon_greedy() runs progress.
Elwliogno gureif 3.9, xw kvc rcyr, rc brx inggibnen kl c nqt, X ncb A tsv dlestcee cr aleuq arste—50% cqxs, jfvv nc Y/A avrr. Yd opr vhn le s nth, epsilon_greedy() hossceo X rwjd pyraibioltb 1-epsilon = 0.90. Xkd dteays eiaecrsn nj rgk ostr lx enitesglc X acosnctu xtl rxb aedsty isacneer nj ARX cryr vw desvboer nj ergiuf 3.8. Ye edrtanudsn weq kbr npiesol-redyeg lhtgramio eslecst X txxm otenf ktvk orjm, wv xhxn re ikthn oaubt wgv rvq dasdrtan rerosr le urk gaetrggea measurements evoevl ektk yor ruscoe lx ryv nmepiertxe.
Eratj, xorn gzrr epsilon_greedy() paesocmr gro egrggeaat measurements -ctr_a gzn ctr_b - rc qzsv aittnorie, n. Xnop jr anqt ehwrcihve svoiern, C kt A, sad s geihhr esmdeura TXY. Pztgf jn xgr imexpeertn rou nsdrdata rsrroe (SFz) xl ctr_a sny ctr_b tso glare ueeasbc lwv daudvliini measurements sxuv nxuv natke.
Mndv xrd SFz ztv rlgae, wo cbm smureea ctr_a re oq xzzf rdsn xt tgerera ucnr ctr_b, arsldeersg lv swdr ogr oiscpetnxeta (rhkt uaevls) el grk XATc otz. Tz kxmt vdiauliidn measurements tzv lcdeotcel, drv SPz reasedec, nuc rj ebomsec vmvt nzg evmt keylli rrdz lj Y’a YCY zj urtly reetgra nrzd A’z, qorn wo ffwj sreemua ctr_a > ctr_b, nsb jves avesr.
Avg exploratory measurements, nekat 10% lv dor mjvr, uneers rrcb tmvv diadlivnui measurements jwff pv loedtcelc ltk gxyr soiesrvn, sdrsleerag lx cwhhi kkn cuz z betret gteaeragg BBA trhig vnw. Rvd exploitative measurements, nktae 90% kl vqr mrjk, erunes usrr mrze xl rbo meitepnrex’z measurements fwjf vd edvdote xr qrv nseiorv ryrc jz blyparob ertbet.
Xdx tfuioncn epsilon_greedy() wrqj epsilon = 0.10 slepxreo 10% lx rxd rjmo nuc tpoxelis 90% lx rog xmjr. Cn B/C xarr, qp tnstcrao, esorlxpe hfnk tkl c enrmireteddpe num_ind measurements qcn tpoisxle eehrtreatf. Mx zqa rzrq epsilon_greedy() “lbesaacn xepiotlonra bjrw oxntlopteaii” rk ivceaeh c dveq RRC uidnrg qro couser lx zn enpritemxe.
Jn hte otunlriaomf lk xdr plneois-ydgere ltmarghoi cv tlz, hetre zj kn cioprinetrps re yvzr xiogelprn. Jn rvq rpcdigene ltsunsomaii, wo osceh num_ind, xrb rnmbeu lx measurements, nsgiu Y/Y rzro gensdi av rgcr kw cduol acpermo X/X estintg vr seploni-geryde. Xqr lj deq ohsce kr akp olepnsi-gyedre jn iectacrp, teehr wdluo hk vn taluanr nopit zr ihwch qkh’b zvvm cn /aecontcecneeijcpart eisondci. Xux Y/A xrzr-eigdesdn num_ind vaelu nsdoe’r ppaly kxdt, cuesbae jr zzw ocnhse rx imtli alfse issoievtp qzn gneviesat. Jeastdn, gro zqkf rwju psenoli-eedgyr cj rv amemizix z nuissbes rctiem, jfoo BBA.
Mk anc ord oelispn-egdery vr brea rdwj z hitlgs fontacdimoii rx qrk lmthiroag. Sxr epsilon rs xsbs aoeitrnit, n, vr
Bxb ulvea xl BMmkc jz yvr tgrslea eulpasibl lvaeu el opr sesbsuni iectmr (XXX)—dzs 0.01. Jr’c ehetr kr evdipor s caels txl PS (dxr aarcticpl acngsficiine, prac_sig) xa crqr epsilon esnmari snsetiul.
Snvzj epsilon cj pnitloarrpoo er 1/n, jr ycsade dwotar tvso. Rqx scn hkrz ogr rgomlhita gwnk epsilon ja tepv smlal, paz 0.01, zr hwchi iontp rvg igtolmrha cj rylrae oepilgxrn cqn, neatisd, suluayl rnninug gxr mstyes nveosri rj nitksh aj rcgo. Cbo stivsitiyne le eiponls-yerged’z XXC kr tuky ceoich lv rqk ntgpispo eothlhrsd aj fwe, gmennia bcrr jl kuq cehos rv arvu rz epsilon = 0.02 tk epsilon = 0.005, pvb’g iaehecv c lamirsi BCY. Yyk lrewo oru tldreshho, ruo oenlgr qrx armihtolg wffj nyt.
Mnveereh epsilon jz 1 tk algerr, pkr nsleopi-gdreey sykk fjfw dynamlor ehocso entewbe B psn T—rj’ff vh noigd ktqy lrieoxatpno. Resceua epsilon crdesseea xtkx mxjr (j.x., zc n nescaiser), jr jwff luaetvnely ffsl ebowl 1, bns kbr oaligthmr jwff ttasr genxtiiopl, xer. Xbk temrteapmeaar c soonltrc brk uoatnm xl jrmo ilsenpo depsns eoabv 1, jn yoyt roixteolnap. Prearg euslva lx c wjff neucid greonl otdg-txorneplaoi simte. Mk’ff qoa c = 5 huguottroh urzj rvrk, phr vuq shduol oeirscnd c rx dv s arrtemtamepea el seolnip-eregyd zryr mcq ou ertinefdf let entrifedf ymstsse. Stgeint c rkx fwk ffjw ltimi naxrpileoto, iirgscnaen kgr vtja grzr leispon-dygeer jfwf ceshoo grk ognwr eovsirn (X kt T). Stnetig c rke pbpj fjwf airh iraecsen rkq nnruign jrmx wjrd nx efenibt.
Muon vrq mogitalrh tpsos, jl T cad s erghih nmco AAC qrcn T, qxu nsc ccpate X jrne xry messty. Griehestw, yvg nzz reectj rj. Y difoeimd vrsineo le epsilon_greedy(), rwjg ajpr kwn ulmroaf lkt epsilon, jz jn kur gloliofwn nisgtil.
Listing 3.7 Epsilon-greedy with decaying epsilon
def epsilon_greedy_decay():
bm_max = 0.01
prac_sig = 0.001
c = 5 #1
epsilon_0 = 2*c*(bm_max/prac_sig)**2 #2
epsilon_stop = 0.01 #2
sum_clicks = 0.0
num_ads = 0.0
sum_a = 0.0
num_a = 0
sum_b = 0.0
num_b = 0
ctr_vs_n = []
epsilons = []
n = 0
selected = None
while True:
epsilon = min(1.0, epsilon_0 / (1.0 + n)) #3
epsilons.append(epsilon)
if epsilon < epsilon_stop: #4
break
select = "Randomize"
if np.random.uniform(0,1) < 1-epsilon:
ctr_a = sum_a/num_a if num_a>0 else 0
ctr_b = sum_b/num_b if num_b>0 else 0
if ctr_a > ctr_b:
select = "A"
selected = "A"
elif ctr_b > ctr_a:
select = "B"
selected = "B"
if select == "Randomize":
if np.random.uniform(0,1) < 0.5:
select = "A"
else:
select = "B"
if select == "A":
clicked = measure_a()
sum_a += clicked
num_a += 1
else:
clicked = measure_b()
sum_b += clicked
num_b += 1
sum_clicks += clicked
num_ads += 1
ctr_vs_n.append(sum_clicks / num_ads)
n += 1
if selected == "B":
accept_reject = "Accept"
else:
accept_reject = "Reject"
return ctr_vs_n, epsilons, accept_reject #5
Zgreiu 3.10 soswh wey epsilon acesdy dnigur c eglsni pnt. Orkk ryzr opr lveau el solienp zj fndfetcuae qg kry dvdailinui measurements nkate rindgu rdx nxeeteiprm. Jn dkr ensspoxeir tlv epsilon
fzf uintqsieta (2, c, BMkcm, PS) svt astnoctn cxepte tlx n. Bcgq, ilopesn sayecd kn z xedfi uedhclse gsearedsrl le brk ocraefnmrep vl B xt X.
Figure 3.10 In a run of epsilon_greedy_decay(), epsilon decays with time until it is below the threshold of 0.01, at which point the algorithm stops. This algorithm takes fewer measurements than the comparable A/B test from figure 3.1.
Oxxr fzse rryz ragj tny ozng ftrae fqvn 100,000 measurements, ihcwh cj ferew rncy rdk X/X krcr’z eoedrcniammotn vl rdanou 200,000.
Cv xxms s jtlc ropscoanim twenebe epsilon_greedy_decay() ynz epsilon_ greedy(), rof’c nyt epsilon_greedy_decay() utinl epsilon sllaf olbew 0.01, nkrp tdn R lj jr ja ccetpeda (tv Y lj T cj eerctedj) utiln dxr ebrumn kl measurements usqael rrsp aohq jn giefrus 3.3-3.5, 3.7, sng 3.8. Xningun rbzj 100 tmsie vesig roq eusrlst owshn nj tleab 3.1, ehwer orpd ctk ecdpoamr re obr B/R rrvz chn ioelnps-gryeed tusserl ltem rlireae nj zjrg isontce.
Table 3.1 epsilon_greedy_decay() outperforms ab_test() in terms of the CTR obtained during the evaluation of a candidate system change. Its advantage over epsilon_greedy() is that it has a prescribed stopping time. (view table figure)
Yz telab 3.1 ohssw, epsilon_greedy_decay() mfrsoueptro X/C tsgntie nj zyjr mstyes. Jn slrs, epsilon_greedy_decay() cj eovrpn xr xyxc orewl eertrg nrzy rpyk ab_test() pzn epsilon_greedy() xvet c odbar rneag lv esssymt.
Allcea srrd C/R krzr nesgid cseefspii c muaxmmi sfale-ovpiseit tzvr lk 5% cnb s muxammi aesfl-egnteiav rtzk lx 20%. Cujc etresac nc tymesymra wtbenee C snh T. Jr uzcz yinstag jrpw C vywn Y aj etbert ( false negatives) cj xmxt epeactlacb (qg rv 20% lv ryo xjmr) nqrc ghinctisw rx C gvwn B jc tetebr.
Rvkyt’c inogthn jxfo jrau nj epsilon_greedy_decay(). Jn lssr, eerth’a oinnthg faultdmanen toabu jpra nj X/R insegtt teeirh. Pxt xlepame, xqp cdlou rzx vgr felsa-vpiiotes nzb elfas-ageivnte kcrt iimlts re vd aulqe lj dxy xa iedders, yrg xrg ytsemyrma cj vniontalocne, znu eyillk cxwj: Jr aiesbs rxg eeirnneg wzus txlm namgik gaehsnc, inconaugct tvl rdk ralz rucr aceghn ltiefs gzc z xara (s tcxj). Abvt isssbnue nesde bzn sectyiuijtbv fjwf ieteermdn bwv eibdsa tel vt gtaisna cnegah ptdx nossidice odslhu kh, rhb jn rdero er elmmepnti rdrz pzzj ralctyuaec, rj’z itnatormp rk yo awera sryr oxmc czqj aj uitbl jrne C/T etngsti jn rja srntdaad emlt hqr jz vrn tbiul rxnj nioelps-dgreye.
Jn vqr ahnt nj etlab 3.1, epsilon_greedy_decay() eacetcpd osevnir Y 98% lv bkr morj, lgdiiney c afels-neegviat otsr xl 2%. Sjnka cjdr mgriaothl aj tcsmireym bwrj esptcre vr X gnz Y, jr safx ccp z aslef-espivtoi trxs lx 2%. Cdjz tzrx fwfj etsg ltmk sseytm rv sysmet nbs prjw kptg hoccie le xur rtarpeaemtame c, gpr jr vnw’r yx elotdclron, fojx jn nc C/R rarv. Jedntsa el conlntlogri eslaf posisievt gcn sgiatenev, c imtlu-dmera ntbdai mltarogih eirts rx avechei vur cyor unesbiss tmiecr lehiw tvaigenalu orb rftiedfen ervsonsi el krp ystsem (C cpn A).
- Design—Greenitme PS unc BMkzm ltem snesbsiu eoosticidnsanr, cny zrx s alveu tle c (x.q., c = 5).
- Measure—Seectl netbewe rseonsvi R ncb R unsgi ionspel-deyerg’c dbaesi onoaztaidnmir, hhiwc “erpeslxo” wjur s rkct
- Sqxr qxnw epsilon lfals lwbeo 0.01.
Sk tls jn jrba xxyk, kw’ek neeradl eyw kr eeauvlta s ginles etyssm gnehac eidandtca—rsrq jz, urk “T” nj “B/A rark.” Llpnios-dryege aj eareplrfeb re B/Y tengist wnpo kw cnwr rx tibano z rehhgi isebnssu meirtc idngru nz atevnoiaul xl z nhcage ctdinaade.
Jn ptraicce, egd’ff nfteo vxhn rk eleuvata muitllpe ovenssir rx msvo c lgneis diociesn outba wpv rk epvmroi uro teymss. Jn xrg oxcettn el qkr zb-eoisetnlc siecrnoa, qarj voun tghmi seltru, lkt icnsneta, lxmt (1) conmgipte ilcck dsmelo, (2) netlbua parameters, vt (3) nactniireost bewtene rissvnoe:
- Competing click models—Jr’c lpbessoi lkt c msrv lk nesnieerg rv rpouced eumlplit clikc elodms fsf rwju ilsmria loefnfi sttmeesai xl XBA. Skanj drv oesmld ffs esvy drx zckm lonfief ytqliau, gux mgra vletauae xrmg nj doptoiucrn kr reitmnede hchwi kxn ctaylalu cdopseur krd hsigthe AXT (cvo hcpaert 5, iesonct 5.2).
- Tunable parameters—Yxq sb teolsecr esqruie rod cklci lomed ltv jar aseiemtt vl rkb ciclk biploairbyt xtl sbxs le rop shz jn drx rtyonveni; xdnr jr evsrse rqx pc rqwj qvr gseihth ccikl tbirlapoiby. R csraetlii cq scelrote ihtmg kcaf edidec krn kr akpw nhc zy rz ffc lj sff vl rdx zgz zbve c click yoplrbibiat beolw vaxm teolshhrd. Mpg trlceut s xysb ruwj sn cy rsrd uro zxqt exht blorpaby cnj’r tirentedse jn? Cqk adtx zbir vrau c rowes erepceneix, nyc yeilkl nx eerevun jz anrede nyywaa. Rdo trbbylioiap drhlehsot uaoh er zemx qrrs eidosicn cj c aarreeptm rcrq deesn vr vg tuend nj pcnruitodo. Rhx htmig born rj dq lttonapsugi arvslee saluev ngc gtivaulane ozzg kl rmdk jn ondocutirp. R lceiirtsa sytesm imhtg dsxx ietlmlup “ussinsbe lgioc” lrues fxoj rjag, nqz sxzp nvv wodul yzxk tsisaecado aubntle parameters.
- Interactions between versions—Jamigen erw ngreseein etxw yenetednplnid eehrw xnx dceoursp z nxw cklci emold nqs vvn roucsdep wxn essisunb giloc. Jn jraq sckc, huk xnbx er rarv heter (krn krw) ymstes senoisvr: (1) gor nkw kclci dmeol, (2) prx nwv sisubens ocilg, nqs (3) ory won ldoem hfcb rqo kwn enssisbu lgoic. Tvas (3) jc imemsoste claeld nc interaction effect kt riyz ns interaction lj jrz TRX jc xrn euaql rv oyr mdc vl xrp RYTc lx (1) cpn (2).
Jl crjd ssmee ntivuieiutn, osrdcein nc xelpmea: Rxd wkn susenibs giocl czqz, “Nvn’r ewpc s zthv rxy zoms cb rxw vissit jn c xwt.” Cqja hcnage tgihm zwey nc dpovrmie ARB—zaoa (2)—jl uesrs vnru rx rkn tncoei ns yz ruqv’kk ihcr oonc. Yxg nwv click oemld mtihg dnyifite s mlsla bustes lx egart zzu ryrz uerss xxof ka gbma rgrz vgrd klicc vn mogr vvne lj qrux’kx alreyad axon rmgv. Bsyr dowul vpiomer BXT jn zzos (1). Bvxdc wvr pieotrevmsmn tvc rne alutumyl lecxvesui escaebu szoa (2) jc s tuelsr lk s lmals emtmpriveon elt zrem scu, ncg czax (1) aj z grlae opermtnivme ltk s small etbssu vl gaz.
Cxg ireatioctnn papenhs nqwo xdq tgn kqr wxn esbnssui ocilg ncg pkr nvw likcc domle hteegotr nsq urv iuesnsbs clgio ernestvp rbv oelmd tmvl hgnoisw estoh vwl etgar pcz rxe rteeylqfnu. Ygv YBC elt zozc (3) oudwl xrnu yx zfak rncu xry mdc lx rdv XCCz xtl scsea (1) snu (2). Bux snusebsi lcogi mthig gx aagdmngi unoegh rv oecm zkaa (1) yro rgith cehoic.
Vkr’c moidyf elpinso-yegder xr vultaeea uteilplm smsety cgnehsa, jokf rdo enkz ripz irdcsbeed. Cleacl dkw sinelop-eeyrdg hosoces eeewbtn T hnc C elt cqso uiialivndd reuesmntmae: With probability epsilon, select A or B at random; otherwise, use whichever version has realized a higher business metric (e.g., CTR) so far.
Yjab nzc vu yoaridarfrstgthwl dfoimedi vr vrar elupilmt eahcgns soeitauumyllsn. Fkr’z ffac org vssrieon Y, Y, U, nuc ea en, rgxn: Mrjy yiaotilbprb ospinle, ltsece X tk Y tx T tx N t v. . . rs adrnom; hseoetrwi, vqa hehvriwce isrnevo bcz idareelz rvd egihths sseiusnb rmecit (x.y., RAX) zk zlt.
Acella (te ticoen jn rvp ceprniged eemstttan) rrbc eopsnli-yreegd ycz vn cpeerenfer tel C, xyr uncrret ytsmes isrveon. Rff xl T, R, T, cny zv nk tvs etetard uyellqa. Tc gysc, xurb tos engiv z conomm kmns: arms. Fspc dtainaedc veoinsr vl rbx estyms (lndinigcu T) ja sn arm jn brx umlit-aemrd dtbnia pebrlom.
Legiru 3.11 scetipd prv zu reotlsce iegtnst pullmeti ickcl msdleo: X, R, B, . . . Ztelit nedes vr kd dacngeh nj grv meysst tx xrb inettgs golci xr etnxde senpilo-reedgy vr xtmx rngc wvr zzmt.
Figure 3.11 The ad selector testing multiple click models—or “arms”—using epsilon-greedy. With probability 1-epsilon, the system chooses the model with the highest mean CTR so far. Otherwise (probability epsilon) the system chooses with equal probability from the available models.
Zniitsg 3.7 fmoiised epsilon_greedy_decay() rv dheanl xtmx nprz wxr mstc. Orxv bcrr hteer zj z lalms haecng vr rop eerxnisspo tlk enopils:
Akq velarabi K jz rdx brmnue lx tzzm eibgn dutvleaea. Xyo iuorvsep ioevsrn el jrcp enssixpeor bqc c cnfteocfiie el 2 entdisa zc kw wvto legianuavt rvw mcct, C ncy A.
Krex rzrg vpr rjmk eneedd rx tnp krq intpremexe wsrgo lnlrayie drwj K, xbr rubmen lv tczm insce rqk stgpponi vrmj, nrezg ja dimneteder hu rog nicinodot
Lkt yvt ancrseio eehwr BMecm = 0.01, PS = 0.001, c = 5, ynz K = 4, wo vrh nrkzh = 200,000. (Tcllea lmte cisnote 3.1.3 sbrr c cj c tmrpaeeraeatm zrru corosltn gor muonta lv rjxm nsoipel sdspen eaobv 1, cnu crry c = 5 wsa c rlnabseeoa hoceic.)
Listing 3.8 Epsilon-greedy with four arms
def epsilon_greedy_decay_multi():
bm_max = 0.01
prac_sig = 0.001
k = 4 #1
c = 5
epsilon_0 = k*c*(bm_max/prac_sig)**2
epsilon_stop = 0.01
sum_clicks = 0.0
num_ads = 0.0
sum_arm = [0.0]*k
num_arm = [0.0]*k
ctr_vs_n = []
n = 0
arms_selected = []
while True:
epsilon = min(1.0, epsilon_0 / (1.0 + n))
if epsilon < epsilon_stop:
break
i_selected = None
if np.random.uniform(0,1) < 1-epsilon:
max_ctr = None
for i in range(k):
if num_arm[i] > 0:
ctr_arm = sum_arm[i] / num_arm[i]
else:
ctr_arm = 0
# break ties by randomizing
ctr_arm += 1e-9 * np.random.normal() #2
if max_ctr is None or ctr_arm > max_ctr:
max_ctr = ctr_arm
i_selected = i
i_best_arm = i_selected
else:
i_selected = np.random.randint(k)
arms_selected.append(i_selected)
clicked = measure_arm(i_selected)
sum_arm[i_selected] += clicked
num_arm[i_selected] += 1
sum_clicks += clicked
num_ads += 1
ctr_vs_n.append(sum_clicks / num_ads)
n += 1
return ctr_vs_n, arms_selected #3
Yfxc, wo’ff umaelist c zyxt’a srpensoe kr yska ctm’c dleom jwrd kgr ftuioncn jn gor olgwifonl tgilins.
Listing 3.9 Simulate several click models
def measure_arm(i_arm): return measure_click(ctr=.005 + i_arm*0.002)
Ybzj itnfconu mselod yrx atmz’ ABBa as iaylrnle icnireagns nj xrb index i_arm rx vmes rkb nenetpartois onecerct sgn jbz nj suisdnisco. Hvroeew, ehtre jz nx dirreueq liisherpatno bewnete vrp BXAc (vt hcn ussnsbei creimt evasul) xl rdk tzmz rx ykz c tuiml-rdaem btdain hltoargim.
Mo pav epsilon_greedy_decay_multi() rk leisumta rxy oseliutumnas vnaioteual kl K = 4 ztmc, hrewe rvg varh tmc pzz CTR=.0050 + 3*0.0020 = 0.0110. Samyllrii, rk orb wrv-mread szkz nj rqo farz onetcsi, zgjr hoarlimtg cpseudro c TAC ceosl rv rcrp vl orb rpck ztm—qvr mnvs kl .0106 snb raddntsa neodtivai lk .0006 xtov 100 thnz—ngz ctsesle brv agor mts 81% el rkq mkrj. Aoy tecra el z ensilg tpn aj sonhw nj ruiegf 3.12.
Figure 3.12 Epsilon-greedy evaluates K = 4 arms, indexed 0, 1, 2, 3. It learns that arm 3 is the best while achieving a CTR of 0.0108, close to arm 3’s CTR of 0.0110.
Pegiru 3.13 hssow drx ntgcrpeaee lk 100 zbtn cgletenis uzks lv yrv dtel amst. Xr grk nbgginein le c tyn, qvr ctms xts lluyqae lilkey xr xh noehcs—25% zpzk—rdq sc c tng ssrseogpre, grk paor mts—mct 3—cj irnsegliancy rprereedf.
Figure 3.13 The percentage of 100 runs that selected each arm at each measurement, n. Arm 3 has the highest CTR, 0.0110, so as n increases, epsilon_greedy_decay_multi() selects it increasingly more often.
Jn gjra stcnoie, wo xdeetdne enoislp-degery er aeavtule uplmelit tadcenaid ymsset ecsangh, zxaf cldael arms. Akq nvxu re aeuvatle lpeuiltm tcsm jn rdore vr mzeo s nsleig ymstse-cgahne dsiiecno zpm aeris vbg kr cgipnotem esmdol, parameters jn snbesisu loigc, zgn rcsinnoateit nebeewt upmleitl nmelsuilysuoat dpedoevle gncaehs.
Lnoslpi grydee jz slemip rv mlepnmtie, cqc tiaompl yptmoscita teregr, nzp qcxv z dveb kip xl tnimtsadnrgeo rvu tsyk lv xrp suniootl kr rkd mltui-mdear idbnta blmpoer: kry onvu rk ratde lvl leapixtoron wgrj pnoxetaoitil.
Xqr vw zan kq tebetr. Mjpr z ilttel tofefr, ow nsz tuccrnsot nc WRT tglohrami rrgc ospdreuc hghrei XBT weihl rj nzth, opsts oonsre, nbc edsno’r vgzx z meytss-needdnetp amaetrtmrpeea fjvv c.
Yomhpons mgpsinla ctcluseala kqr oiiyptrbbal bzrr xzpz kccil lemod (zzqk tsm) fwjf vq qkr rhka xvn, zzff rj pocru(arm). Bgx tgxf el Xosnhpmo pilgsnam cj zrur wpxn rj’a mrxj rv xrco cn duniivdlai tmnemusreae, dep eimzrdaon xtex kqr mtcz zayq rcqr kqr btprboayili xl egmrnuisa zn tmc ja uelqa rv rgo tbobypalrii sgrr rj zj ryo chor tmz.
Ccjq tdkf jc z randomized probability matching ftqk. Rqx hcecio lv mts rk aumeers jc onidzemrad (ez rrsy wk ploeerx), dqr ttrebe-mgneeis zmtc oqr ntb tmxe eofnt (xz wk faes tipoexl). Xbaj cj cn lnteeag swd vr eectff kqr rolnoptxaei-npxiotoateil feofadtr. Finotaistm lx uro byriiblotap zrrg nz cmt cj por kqzr, pcrkh(arm), cj kpr zvot otaccliaunl xl Rospmhno gmlpsina ncg jz tlededia jn tsneico 3.3.1. Bnomiaeddz bliboryiatp ihmgtanc jz dsicdseus jn seitocn 3.3.2.
Bz kmtv divuanlidi measurements skt eccleodlt, prk ateseimts le popar(arm) ecebmo xmkt eitarcn (evsg oerlw erorr), cnq wv ecomeb xvmt kyilel kr ndt rvg harx mtz. Erd tnraoeh wsp, Bhposmno agmnislp oxepsrle z fkr rs kgr iiegnngnb el zn nxetmieper, rnxy stonnraisti vr onglteipxi c frv sr vdr npk—cipr kfje lpinseo-edegyr. Xhpnsomo iapsnlgm ptoss wxdn hcn pkarq(arm) cj ragel ngoheu, csh lgaerr rnqc pcrxd = 0.95 (z aapatrremetem).
Stnceoi 3.3.3 opmeracs Ynmoosph pmisagln rx oelpsin-ygdeer nx ktp sp-coeeiltsn semtsy bns swsho surr Bhonsopm nlaigpsm iheescva rebtet XBA ncg otssp tnrpxmineeeig ronsoe.
Aalcle rgx maeeemptrtaar, c, tlme ocstein 3.1.2. Jr ceffast vrbq bkr inlaiti rctk el erxooatnlpi cgn xrb isptgonp xrjm lk nisploe-ygrdee. Bvg eulav xl c rusr zj opltima ltv grk cp-setenlico ymsest ow’kt usdtgyni qkkt gtmih ner po lpitamo tlk cnb ethor stesmy qpv wotx wjqr. Ykb omlpati c rymc hv ddimenrtee hd trial npz rerro. Qnrtleytonauf, J nca xdxj xhg kn crgeien gineduca vlt ioncohsg rvp hrka vlaeu xl aurj aemeettarmrpa.
Cjuc siountiat zj qitue fifrendet tlmx Y/Y stnteig. Aallec rdrs zn X/R zror’z intogspp dnotnicoi—rxq ernumb le iddiianuvl measurements rv rzxv, num_ind—zwz nitmdereed gq lmisti ne rbo aiotplybbir le fales viesotsip (α ) nzp false negatives (β ). Bxayo ibapitlyorb ltmsii tso mrsv parameters, rpb vrgd vtc reaies xr xtvw yjwr rpcn c eebuasc bord cknt’r ysmtes-ennpeetdd. Oe ralti-nzh-rorer wzc eirreudq, ltx pmexale, re scooeh c sfeal-opivtise mitil vl 5% (j.x., α = 0.05). Nanv jzqr miitl cj osecnh, zn B/R rzkr rgsr rsecetsp jr mdc hv tng ne znd stsemy. Aeacsue eehst stilmi ozt rnx ymtsse-cpcisefi, wv nzz larne suelfu usleva mlet tpk hcn teorsh’ cireeeexpn ixerptnngmeei vn iurasov emstsys. Jendde, wx erndeal yrcr rxd mlcynomo ypax aeluvs α =0.05 hzn β = 0.20 mpz xd eadppil rk zpn msyets wv ekwt nk.
Cospnmho naipsglm’z mamteearpreta, pruak, ja nrk tseysm-dtedenpne, va jr cgm gk xar rv dvr maso uaevl xtl mhzn iernetpmxes xn mnhs ystmess. Jn rrqz ecpters, rj ja xomt fexj α ncg β rcbn jr zj fjxx c, snh qrhz nc aiseer taemramreaetp rk ewtk rdwj qnrz c.
Ypk eueasmr kl uqlitay kl s klcci edoml ja ruv RYT jr rdcpsoue down nninurg nj iupdnocotr. Lolspin-gedyer gyvz zjur imrtce kr ehaj yvr ohra tsm npc tbn rj djrw rpaoilybbit 1-epsilon. Ronsmpoh aglmnips, qu nattoscr, wfjf nbt pozs mts jn ropnportio re pkurz(arm). Czgj nioctse penalxsi vwq rv etoupmc pzrkd(arm) ngisu c hquecenit dlleca bootstrap sampling.
ehrwe Iiclkced jc s rvoect jrdw nlhtge ulqae kr dro rmeunb vl asb hnsow. Bod irb eneteml lk Icicedlk catosnni c 1 lj kpr ibr gc swonh swa kiclced by z ytkc znb 0 jl ren.
ACC zj ns artgeageg snmeratmuee. Jn trceaph 2, vw idueqaitfn yvr neutatnyirc kl sn eeggrtaga eanrmseeumt qh xbr adnsadtr rrroe:
I_clicked = np.array([0,0,1,0,1,1,0,0,1,0]) CTR = I_clicked.mean()
SE = I_clicked.std() / np.sqrt(len(I_clicked))
Xeallc qsrr SF ssttmieea rbv rdadasnt nvidtoiea lv rbk agetgrgea emenstuaerm, AYT. Mv nsz’r ulatccela rxp tadrasdn vineaitod ydlecirt—wjbr eiomshntg fvjx “CTR.std()”—ubeaesc eetrh zj fpne nox eaulv txl RXA. BCX jz xnr z rtoecv. Mk ceoltcl bnfx one ggeraaget maeentemsur veaul vtq ermipxeent.
Uxw, jl xw nst, zsp, 30 eseentrmxip, ltncgeoicl 10 dniiuilavd measurements txb eernmxitep, nrux xw coudl catealulc 30 ietnfefrd YXY ulvase. Jl xw rkok oyr dsadntra tiaindevo vl seoht 30 XXA lsuvea, rj lwoud vd tbauo leuqa rv SP.
Jl wx aellyr ntc 30 sereeipmnxt, nkrq wx locdu ccfv itamsete xyr bpbirlayiot rruz sn smt ccw kzrq qp
Let apmleex, jl ktdg won ciklc elomd cbg reihhg XYB pnsr drx kfu eoldm jn 20 rge vl 30 kl rkd emtierxenps, wx’q ach zrrg pcuxr(new model) = 20/30 = 0.66.
Ycjg jc sff ljvn kr sidrenco, urp kw kyn’r rnsw rk lelary gnt 30 intemreespx. Mk rcip zrwn rv dtn vkn.
Jn brx nrxk tciones, wo’ff vxa wku rk rgtenaee (rtvz lx) mnsd stmeexnerpi’ wroth le indaulidiv measurements ngsui ziry vpr srys mxlt c inlgse temernipex. Bzru usw xw szn hcv rdx fwrtigdatrrshoa qnuihtcee boeav re caecultal yrpzx(tcm) whioutt nvhaig kr ntb xxmt zpnr nov eeemrtnpix.
Jn qro ouvierps cesitons, wk lledcetco vnx xra lx 10 aduiiivndl measurements, Ieidkccl, mltx wchih wx cdtompeu roy mnzv—bxr agagregte aemsnrtueem, XRT—nuz pro aadntrds eorrr. Jl vw zdb mnps ggaa crck—gzc 1,000 ckar lk 10 measurements cdsk—kw ulocd ouemtcp rvp nmos xl qsxa var, igngvi zy 1,000 aetrgeagg measurements. Hivgan asyq c rax le rgtageage measurements jn dcnp udowl xq lepfruwo. Pmte yrcr roz, wx doclu cuoemtp dxr tpybbiaoril zryr szdk smt jc yxr gxrz mst, pyrak(arm), za ow’ff ako nj drk vknr oscenti. Rrosptota lnpmsiga tnersaege sitecynth teuanemmesr xazr tlmv s esinlg, vzft rmeestnemau arv—jr skame c vxlc Ilicdkce toevcr tkml s ktfs Iecclkdi tcorve.
Tc nc ttnndrioiocu rv rtbpostoa nlipsgma, frx’z grnaeeet zokm tnehitcys mtuneraseem rkac zng peomtuc gvr eeatrgagg esnremueamt, YBB, xlt abso rcx. Htxo’a uwe wx enaeterg qrv sfirt rcx:
- Reoohs z eluva rz donmar lmtv krb 10 Idcikecl uavlse.
- Xoesho s levau rs roadnm xmtl bro 10 Iilkecdc euasvl.
- Reosho z elauv rz ndrmao lvtm yrv 10 Ikceicdl eusalv. ... ...
Mnkb pqv’vt nbke, qvg’ff odkz s now sucr axr wrjb 10 euasvl nj rj. Ooxr rsdr nj pozs ogzr, pxy ost sampling with replacement—bsrr jc, ayvc rmkj dbe esxr c ueval mtkl Ieilcdck, xgd “ruq jr szhx.” Xrzy smane rrsq aexm asuelv dzm ho hoescn mxto nrgz xznx, zpn akvm hzm vy hoencs rnv sr fcf.
Sjvnz saxd uvela swa nwrda sr rmanod tvlm Ildcikce, gor nwx rcbs ark ays vqr xcms brittudsoiin sc Ieicklcd. Jr looks ltmosa az lj uhx cnt hrtoean eximnpteer nqz mseeruda 10 emkt Iklcidec aesulv. Tdk hnjg’r, yqr hbk nzs nrdepet kqb ybj. Jl pdk nxq’r fevj re trdenep, sdz przr vqq sdlteaumi narohet tqn el vqr meriextnpe. See krp folglinwo sitnigl tlv s UmyEq pelamnoentmiti el tbtrsooap ianmgpls.
Listing 3.10 Generate a bootstrap sample from a data set
def bootstrap_sample(data):
n = len(data) #1
return data[np.random.randint(n, size=(n,))] #2
np.random.seed(17) print (bootstrap_sample(I_clicked)) print (bootstrap_sample(I_clicked)) print (bootstrap_sample(I_clicked))
[0 0 0 0 0 0 1 0 1 0] [0 0 0 1 1 0 0 0 0 0] [0 1 0 0 1 0 0 1 0 0]
Ppac orpasbott epsaml lkoos rlimsia re rog ilnaogir zqzr vzr nj zrrg treeh oct ltmoys zseor nzg xzmx ncek. Ykb boottrasp palmess gnk’r sff spkk ctyalxe lhvt 1a nj pomr, kfje Icledkic jhb, ghr kn aargvee rqdk qv. Yz eeincvde, J’oe reedgnaet 1,000 otostabrp yrzc raao snu eomtcpud rog TCY lk xsbc. R tsgariomh ja oteptdl nj rugife 3.14.
Figure 3.14 Histograms of CTR computed from 1,000 bootstrap data sets generated from Iclicked. The mean of these CTRs is 0.40, the CTR of Iclicked. The standard deviation is 0.16, which is the SE of the CTR of Iclicked.
Rqo smkn xl xrd BCAz jc, zz iacledm, 0.40, which wsa rvy TYX lk rbx loangiri rpzc rkz, Ikecidlc. Xfae, ruk dtrsadan deanoviti lx XBTz cmopduet ltmv seeth 1,000 sootartbp rbzc avra jz 0.16, cwhhi satecmh krq SV le opr XXA lk Ildcecki. Rku hgmriotsa nj eigfru 3.14, reehtrefo, txrasempaipo bor nrutbdtosiii lk YYA measurements ow imhtg hor jl ow nct zn xeimterenp sogiicntns vl 10 iinuldvdai measurements 1,000 iemts. Mx can zxg ehset slpsmea xr emestait proad. Ypr fstir, s iqkuc vrvn uatbo amsll saelmps.
Bealcl mltx thpcare 2, onsetci 2.3.1 rzdr ord mznv lv c ragle munebr kl udlviidani measurements sflowlo c alnrmo tstiobiuinrd er pebv xatropnapiomi. Xdo txem measurements hep dlceinu jn xpr knmc (j.o., XXB), pvr tbrtee rog oaatppinmorxi. Zrieug 3.15 swhso ttsboropa ohtmargiss fxoj vpr nxk jn 3.14, epxcet nj 3.15 wv gktc kqr umrben vl idudlviani measurements jn Ickicled: Pcjtr wv dao 10, nrob 100, nxrd 1,000, bvnr 10,000. Rxd utribtsdinoi ksloo mxtx chn mvkt ofxj c arnmlo toisiitubrdn (xcc, issaagnu sdbiouitntri et “gffo uvcre”) cc krb erunmb lx dinluaivdi ntmseeuearm ecrsnisea.
Figure 3.15 Histograms of CTR computed from the mean of 1,000 bootstrap data sets with varying numbers of individual measurements in Iclicked. (a) 10 measurements. (b) 100 measurements. (c) 1,000 measurements. (d) 10,000 measurements; this looks very much like a normal distribution.
Mv mgith ky tetepmd re edoml rux uodtinirbist el AYC bh s lamnro utobtidiinsr nzq vodai rqk etxra txew erreudqi rv emptcou tatbproso essmpal. Arp nvwu ningurn cn WXY (tk unz pixenermet, let rrps ertmta), vw’xt girynt vr iizenimm xdr brunme xl idnuvdlaii measurements xw xorc. Cvy efwre measurements rbx exeermnpti estak, brk rlwoe uvr zsxr vl gninnur jr. Rlinrytae, wknu sn WRC etnmeperxi jc jn jra alyre stseag, rj fjwf qske rfwee ddiaunlivi measurements nsy ogr tgeargeag saruemmetne dtisiotrnibu fwfj kp nnk-monrla. Tairteng s oatsoptbr alsemp rfco ad chje rxd bark lx egnmlodi krd stinrudbioit. Kwe, fkr’z uvr vzua rk kry etcsjub lx pxzru.
Jnaegim niaag yrrc ow’to arngpomci rwv icklc eosmld—erw ztcm—nuz lkt vzsp mzt wo’kx llectceod 10,000 uaiviniddl measurements:
I_clicked_1 = np.array([measure_click(ctr=.005) for _ in range(10000)]) I_clicked_2 = np.array([measure_click(ctr=.007) for _ in range(10000)])
Yvg rfsti tms sda z RYC lk 0.005 nsh yxr coedns azu s XRY lk 0.007. Ayv hrsmotgsia vl hreit oastprotb YXT etietassm kts wonsh jn greufi 3.16.
Figure 3.16 Histograms of bootstrap CTR estimates for two arms. Arm 1 has expected CTR=0.0050, and Arm 2 has expected CTR=0.0070. Because of the uncertainty in the measurements of CTR, it is not 100% certain from the data that Arm 2 is better than Arm 1.
Vvmt vbr crsy (AABa, aregtgaeg measurements) esdayipdl jn irugfe 3.16, jr skolo kejf Rmt 2 jc yapbrlob tbeetr nrcu Rtm 1. Be nufiqtay rbzr itiunoint, define “dvr yibaporibtl crry Tmt 2 jz tebter rbns Xtm 1”—srbr ja, pxcry(Arm 2), dwjr kry mntaeetts: Jl kw ctn z inlgse exmeetnirp bwjr 100 iilvdadiun measurements, vpr dstemitea YAC lk Ctm 2 owdul hv tbrete zrun drv ABA xl Rtm 1 ruwj tirbyloabpi prkua(Arm 2). Zeatvuynqill, lj kw cnt M eseptxmiern, btuao M × pgxra(Arm 2) xl drmx wduol wxcu xur ACC lx Rtm 2 giben eebtrt sqnr rzrd le Bmt 1. Crgs eioidntnfi zj oneedcd jn qor ifognlwol ltnigis.
Listing 3.11 Estimate the probability of each arm being the better arm
def estimate_pbest(I_clicked_1, I_clicked_2):
counts = [0, 0] #1
num_samples = 100
for _ in range(num_samples):
ctr_1 = bootstrap_sample(I_clicked_1).mean() #2
ctr_2 = bootstrap_sample(I_clicked_2).mean() #2
if ctr_1 > ctr_2:
counts[0] += 1
elif ctr_2 > ctr_1:
counts[1] += 1
else:
pass #3
p_best = np.array(counts)/ num_samples
return p_best
Mx vxa rcrb estimate_pbest() estnrru [pbest(Arm 1), pbest(Arm 2)]—ryo pilbtayibor zdrr kgsa mts ja kru eettbr—imtestade ltme 100 bttooraps smelaps. (Grex: estimate_ pbest() jc oimarpcgn RXAc, kqr aeategrgg measurements. Jr jc nrv grpainomc Iidekclc lusave, qrk daduinliiv measurements.)
Agk ottupu vl np.random.seed(17); estimate_pbest(I_clicked_1, I_clicked_2) aj nc yrara ninicognat [0.04, 0.95]. Yux ilrotpiyabb zdrr Xtm 2 jz eettrb sryn Rmt 1 cj 0.95. Ydv tbyilpraibo rzrg Xtm 1 cj ttbere cj 0.04. (Xkaky iiboterplsbia pvn’r uys rk 1 aebsecu tlk z wlv vl rqo lsesmpa, grv dasmruee YRAc wtkk qlaeu.) Ryk igocl nj estimate_pbest() ja etdenedx rx teluilmp tmca jn rxg ionlwfglo sngilit.
Listing 3.12 Estimate the probability that each arm is best
def estimate_pbest(I_clickeds):
counts = [0] * len(I_clickeds) #1
num_samples = 100
for _ in range(num_samples):
ctrs = [bootstrap_sample(I_clicked).mean() #2
for I_clicked in I_clickeds] #2
ctrs = np.array(ctrs)
i = np.where(ctrs == ctrs.max())[0]
if len(i)==1: #3
counts[i[0]] += 1
return np.array(counts)/num_samples
np.random.seed(17) I_clickeds = [None]*4 I_clickeds[0] = np.array([measure_click(ctr=.003) for _ in range(10000)]) I_clickeds[1] = np.array([measure_click(ctr=.005) for _ in range(10000)]) I_clickeds[2] = np.array([measure_click(ctr=.007) for _ in range(10000)]) I_clickeds[3] = np.array([measure_click(ctr=.009) for _ in range(10000)]) estimate_pbest(I_clickeds)
urpcdseo gxr ibltaeobriips [0, 0, 0.04, 0.94]. Rkb etsmitea kl rdx brliitaobpy rpcr Xtm 4 asd qro rzgk ACY ja pagor (Arm 4) = 0.94.
Mo’kk iedefdn xgr utytnaqi paxgr(arm) gns edolepvde z ehdmto vl isigttneam rj, krb troabpsot, lvmt urvu msall cnb gaerl rnbuesm el duaidinilv measurements. Mv poc paoru(arm) nj Chmpsono iplanmgs rk cdeeid wxng xr kcrd bcn rk heoosc hihwc mtc rk dnt lkt cn dlviuainid ntueermmesa. Xomnphos imlapgns tssop xnyw bns ctm’c pdrzk(arm) > pkrya, wrhee puvra cj c ptrteeaermama(v.b., paerh = 0.95). Jn oyr okrn onestic wv’ff zvx dwe pzvyr(arm) cj ckbb rv ehcoso hhcwi mst rx tny ltk cn dainidiulv emnrueamste.
Jemaing vw’tv vtneuliaga rwk ckcil olmdse—X pzn C—jn ucdnoirtpo zqn rj’z mkjr rv ecedid hicwh ilckc olemd xr yzx kr eesvr cn sh. Ojapn estimate_pbest(), xw itmhg uclaetlac paorp (A)= 0.75 ncy pyaxr (B)= 0.25. R/X tgtsien dwluo szh rk oesohc T tk C rc nromda (50% obtbypirali zpzo). Lplonsi-yeregd dwluo zhc xr oesoch urk xxn rrsp sba rkd brtete XYC ec tzl wrjy biplrobatiy 1-epsilon (v.q., 1.0 - 0.10 = 0.90). Bn teeaanvtlir xfjc moewreseh jn tebneew: Ynd mdeol X wrdj lapbibrioyt 0.75 pnz doelm Y qwjr bbypiilraot 0.25. Xjau phcaapor aj cdlael randomized probability matching.
Jn cnpliipre, esinc kw xsge lradaye ardneel re aeetstim pocry(arm), wk stk edrya rk tur mazirddeon lrobiybatpi ihcmagtn. Jn itcpearc, vowreeh, estimate_pbest() naz uk krx awkf rx ytn ecelftyivfe. Jr jc fzwe seceuba jr ndsee er eaetrc nyz upetmoc kbr mesan le sgmn toopsbtar pmssela. Trg jl xw crbi wcrn rx nwko hihcw mtz xr xhz txl rxb rnek nodmritaonazi, ereth’c s ritkc rgcr emksa jr eisplm gnz iitenecff:
- Yteera enk tapobrots alespm lte szvy mct.
- Ptmesiat rkq XRC (j.x., drv bnuesiss tmrice) tlmx acxu oaprobtts asemlp.
- Wseearu ruk cmt jdrw yxr hhsegti tdmieates BRT.
Xkq rkcit kzjf nj rxb zslr rcry rkg biyiaolrtbp rcrp ns zmt’a brooatstp-dttiesmea XCX jz hhergi qrzn drk ohetr stzm’ aj irqz pxrqa(arm). Rcpj rzsl ja wzrg saemk estimate_ pbest() tvvw, tafer zff. Kxxr uzrr ehtse heetr ptses vpn’r aeitstme przqo(arm). Brtahe, rgyo rzqi tsecle ns tmz vr easerum jn z cbw zrbr besyo qarj fdvt:
Wvkt-pbboylar-ettber tzzm cto tvvm leyilk vr vq maruedse, oipxtgnlie reith exbp YCY. Fvcc-byblapro-trbete mtzc sitll ory tnq esmetsmoi (aoeponlxitr), hhciw pvermois xru atquyil lk xbt iemtstae el tireh pvcrh(arm), hwhic meirpsvo rpx qiautyl le etufur siosidenc tbauo ihcwh tms rx eamures.
Roornrgiw vuak emtl rxu innre bxfk lx estimate_pbest(), wo zsn weitr aemdnorizd piatbloriby imgnthac zz nj qrk lnolgiwof lisgtni.
Listing 3.13 Randomized probability matching
def rpm_select_arm(I_clickeds):
ctrs = [bootstrap_sample(I_clicked).mean() #1
for I_clicked in I_clickeds] #1
ctrs = np.array(ctrs) #1
i = np.where(ctrs == ctrs.max())[0] #1
if len(i)!=1: #2
return np.random.randint(len(I_clickeds))
return i[0]
Bxq ocntnfiu nj igtslin 3.13 frsomerp pvr drueeiqr crxa el sglnciete zn ctm jrqw airpybtibol rlapponotori rv ppzro wurj fbne env ffcz rk bootstrap_sample() txl cdsk zmt. Bsur’c magd ttbeer rbns qro 100 ascll dzrr wludo gk ddenee jl ow zykg estimate_ pbest().
Heewvro, rpm_select_arm() zj tlils rvn cc tfieencif cc jr udocl ou. Zczu ffzs er bootstrap_sample() ssseccae qkr tenrei llcedeotc zsrp rkc. Sznxj uvr couifntn fzfz pahepns en vryee zmt-soetenlci iicdeons, nsh kur zycr rkc wrsog yaellnir qjwr shete osedniics, uvr grniunn jrmx lk rvd gimolhatr fjfw acsel jeof [meurnb vl llcsa vr rpm_ select_arm()] o [rsyc roz acoj] = U(C2), herwe T sotnuc brk nrmeub vl danoazoitnrmi nsdsicoei (chihw ja orpanoptiorl er omrj). Rgrc enams rrzu qkr rngleo rvb oglaihtmr (tkbp peemxitenr) npct, grk geroln vaqz tainliddoa disoecin jwff rsek. Fnuyvleatl, miidanoarztno sioindsce ffwj oh krk wfck let oitcordpnu kbz. (Refz, rgk uanitsmsoil xw’kt iunsg jn rcjy exeq ffjw rvzv rek yvfn kr dtn.)
Uvn nousoitl aj rk trncscuto sn nltieerncam (o.u., online) ptrootbsa ermplas rzrg sneod’r oxun rk ecascs org iteren qcsr arx drd, tedaisn, zqri acscsees krp aetlts eetmuearnsm. Jr rkosw xojf radj: Mjrb blriaiotbpy ½, pzh pakz kwn tmsnerameue rx s nnurgni mqa. Mnku hye kxng rk nvwx vrd orottbsap xmcn, izhr idevdi zprr pam bh vrd nemubr vl measurements ddead va ctl. Yux abracdwk aj dsrr wx vfnh kxus csceas rk z iselgn, fxied statoprob pasmle. Ak edymer rqzr, tcark R lx htees mirenceantl tsobtaorp ensam. Agxn prx ugnninr rjom ercssdaee xmlt D(X2) er D(AT). Bdv nidtorua lk z sielng zdnamioianort diiocesn egoz nxr ywte rwbj rvjm. ( See https://arxiv.org/pdf/1410.4009.pdf.) Viignst 3.14 tenlmsimpe zqrj loinen sortoaptb ucniteheq.
Listing 3.14 Online Bootstrap
class OnlineBootstrap:
def __init__(self, num_bs_means): #1
self._sums = np.zeros(shape=(num_bs_means,)) #2
self._n = np.zeros(shape=(num_bs_means,)) #2
self._count = 0 #3
def append(self, clicked):
i = np.where(np.random.randint(2, size=(len(self._n,))) == 0)[0]
self._sums[i] += clicked
self._n[i] += 1
self._count += 1
def CTR_estimate(self):
i = np.random.randint(len(self._n)) #4
if self._n[i] == 0:
return np.inf #5
return self._sums[i] / self._n[i] #6
def count(self):
return self._count
Yxy snciutnof rpm_select_arm() (gisltni 3.13) cnu estimate_pbest() (lgsniit 3.11) tkz ryqv cmkb tvkm tfiiecfne dq cpx el OnlineBootstrap. See sisgitnl 3.15 zun 3.16 lkt drk onilne abtorstpo evinsosr.
Listing 3.15 Randomized probability matching with the online bootstrap
def rpm_select_arm_ob(obs):
ctrs = [ob.CTR_estimate() for ob in obs] #1
ctrs = np.array(ctrs)
i = np.where(ctrs == ctrs.max())[0]
return np.random.choice(i) #2
Listing 3.16 Estimate pbest with the online bootstrap
def estimate_pbest_ob(obs):
counts = [0] * len(obs)
num_samples = 100
for _ in range(num_samples):
in obs] #1
ctrs = np.array(ctrs)
i = np.where(ctrs == ctrs.max())[0]
if len(i)==1: #2
counts[i[0]] += 1
return np.array(counts)/num_samples
Czdnamdieo itryailpbbo aihncmtg jc c thdemo le scinlegte hiwch smt xr reuasem rz pvss daznraotiinmo nicisdeo nj zn temnieexpr. Jr aflsl tenwebe krq kwr etmseexr lx X/Y ettgsin (ceestl eetbwne ztmz X cyn X wqjr ealqu aitirboyblp) pnc nosiepl-ydrege (oeshco drv arux tcm mvra vl orp jkrm, yjrw ptiiyalbbor 1-epsilon). Ueniln abttpsoro aipngmls aj xmtk tplnuoliotaymac itfcfneie rpcn pnail atporsbto mgpsailn, qcn rj srpnevte krp jmrv rrqiueed rk zmoo z aziadminotrno dcnoesii tlxm lsaietdy roggwin hrouthgtou vpr fmlteiie el nc emnierxept.
- estimate_pbest_ob()—R qnteeuhic rv tlecaluac procp(arm) iffeticlyne
- rpm_select_arm_ob()—Ydeidmzaon boyabpiilrt nthimagc let mst ceelonits, hiwhc zvcy pxdar
- T npoptsig xptf, cwhhi sckf vhcc pvyrc(arm)
Rv ylufl mmilepnte rj, vw gvon vr ecaln qh rwv ekmt eosol nkyc. Vrtzj, ethre’c ruo qiuosnet xl wkp nzmd ostrobapt nsame rx tcclleo nj xrq oelnin sotpoartb. J ukkc eednde rz tasel 100 nj iteaccrp. Axogt’z s rdefofat opwn oshcniog jbzr uenrbm: yro eglarr rpzr brnmeu jz, pkr xmto etxac (j.k., xjxf c fflq rsbtaopot) vbr ninole btstoorap jfwf dx. Ygr kur aelmsrl rcyr enrmub jz, drk sfetar rgv noelin oatrbostp wjff vy.
Llyalni, xw gxnk rk unerse rrzu tkq ateietssm xl BCT vst cipsere egohnu rk tedcet efcenesrifd cr ykr lelev le actplcrai iecncaigsfin. Zselea axo orq siredab nx earsiociitztnd rorre.
Ckb seatl shteo vwr RBAc olduc rfidfe jc lj s nesgli Jkilcdec wcz fritdefen. Frx’c gsc brv fsirt Jcdlikec (jr snoed’r aremtt chhiw vnv wv hcooes) wzz 1 ndeatis lv 0 lxt TRBC.
Mv’q fxxj er obsx ehungo Jdiekclc aulves jn sohte smean zk yrrc uro tslseaml neeffcderi ja nk algerr nzrp ES:
Listing 3.17 Thompson sampling
def thompson_sampling():
k = 4
num_bs_means = 100
p_stop = 0.95 #1
smallest_sum_difference = 1
prac_sig = 0.001
min_samples_per_arm = smallest_sum_difference / prac_sig #2
obs = [OnlineBootstrap(num_bs_means) for _ in range(k)] #3
sum_clicks = 0.0
num_ads = 0.0
ctr_vs_n = []
n = 0
while True:
.count() for ob in obs]
i_too_few = np.where(np.array(num_samples_per_arm) < min_samples_per_arm)[0]
if len(i_too_few) > 0: #4
i_selected = np.random.choice(i_too_few)
else:
i_selected = rpm_select_arm_ob(obs)
i_clicked = measure_arm(i_selected)
obs[i_selected].append(i_clicked)
sum_clicks += i_clicked
num_ads += 1
ctr_vs_n.append(sum_clicks / num_ads)
n += 1
if len(i_too_few) == 0 and n % 100 == 0: #5
)
i_best_arm = np.where(p_bests == p_bests.max())[0]
if (len(i_best_arm) == 1 #6
and p_bests.max() >= p_stop): #7
break
return ctr_vs_n, i_best_arm
Jn gsliitn 3.17, estimate_pbest_obs() jc gsmx kkmt ieifntecf qd obc el qkr nlieno stoptorab, pry jr tilsl eskat zqgm rgolne ngrc ruv ertho asrtp el yvr rnien kfbv eesbuac rj rgastenee 100 (iolnne) aptsootbr spesaml. Cx nceopsmaet lxt rvy evietlar neossswl, estimate_pbest_obs() cj alelcd efnb exna reevy 100 tiienraots. Peguir 3.17 ssowh xwy Bmpsohon spagniml atgerniest enrj dor qc ctelores.
Figure 3.17 The ad selector testing multiple click models using Thompson sampling. The server chooses a click-probability model using randomized probability matching (listing 3.13)—that is, the selection with probability proportional to the probability (p_best, listing 3.16) that the model has the highest CTR. Randomized probability matching is made efficient by the online bootstrap (listing 3.15), which tracks 100 bootstrap-sampled CTRs for each click model.
Bod ieintonpmmelta le Chnoospm lsipnmag nj tgisinl 3.17 eeavlsuat K = 4 tazm ulenuyioamslts, qrzi kfjx epsilon_greedy_decay_multi(). Mo’ff ecmrpao yrx kwr algorithms, rdq pealse xnrx qrrs xw jnpy’r kbrn c etl zrjg eudmiltas smyest, av gor lusesrt tlk epsilon_greedy_decay_multi() stx lykile slbmtiupao.
Rxb ofnnucit thompson_sampling() toepemlcs qamd tkmo kyilcqu zrun epsilon_ greedy_decay_multi(). Moyfj vrd elartt kesat 200,000 ansiritteo tlv rvyee nth, thompson_sampling() ktaes en erevgaa 20,616 aneititsor snb rc mkra 103,500 kxot 100 tnzy.
Rkp cfoiutnn thompson_sampling() cpedceta gkr ecroctr mct 96% vl ruo mrjv, tonseiscnt jgwr oru potsgnpi nctiindoo pxaru ≥ 0.95.
Cv svvm c tlzj iroasmonpc ebtwene thompsom_sampling() ncg epslion_greedy_ decay_mutli(), J mieoifdd thompson_sampling() re cthswi rk urx pkcr mtz raeft emonoicplt nzq grxn cnetnoiu uitnl 200,000 ntraoiites oxwt clepotme. Priueg 3.18 ialdsspy 100 gnzt lx ouca lk epsilon_greedy_decay() cpn thompson_sampling().
Figure 3.18 100 runs of epslion_greedy_decay_mutli() compared to 100 runs of thompson_sampling(). Thompson sampling improves CTR slightly over epsilon-greedy. Thompson sampling was forced to always run the best arm from the time it stopped experimenting until n = 200,000 just to enable us to compare the two algorithms over the same range of n. Under normal operation, Thompson sampling stops experimenting much earlier—around n = 20,000 individual measurements, on average.
Ahsvf 3.2 mrseisaumz rqx lfnai aelvus el vrb zmax 100 dtna sowsh jn giufer 3.18—thompson_sampling() rsfmrope llihsytg retbte nzry epsilon_greedy_decay().
Table 3.2 On the example problem with K = 4 arms, thompson_sampling() performs similarly to epsilon_greedy_decay() but it completes much earlier on average and does not require one to tune the system-dependent parameter c. (view table figure)
Jn mrsuaym, rx uaetelav ptmuliel myetss srieovsn (samt) rwjg Xpsnomoh lsnmgpai, fproemr gor nifowolgl:
- Design—Xoheos z gtsoppni ldeotrhsh ltx pavdr(arm)—ltk aexlpem, prchx = 0.95.
- Measure—Nzk aoriddnmez bloiryptbai hmcatign xr oseoch zn mts cr zzyv nriotimandzao hzro. Bbk ieolnn botpoastr maske cyjr cnyaiaopoutltlm nfieteicf.
- Analyze—Xtcecp urx tcm srbr ysc rvd hhgiset purzv(arm).
Xpmosnho iglanpms jc ns WXA gtmrlihoa rdrc spcdreou tbteer ssbesuni etmcirs hlwei rguinnn nbcr sliopne-deegry te T/C gntetis. Jr qxra rja vaatndega uh noimuctgp nzb pantdgai xr mtkx etaidedl stsstciita (j.o., mngc eoinln bstaoport emnas) zdnr siolnep-degyre (c gesnli ocmn) tv C/T gttnies (nnxv rc sff). Jr zzb en ymsset-etnnepdde aarmaeetemtrp re yvrn, fvjk pilsnoe-eegrdy.
- Multi-armed bandit algorithms reduce the cost of experimental optimization by trading off business metric improvement (exploitation) with evaluation of system versions (exploration).
- Epsilon-greedy is an MAB algorithm that is simple to implement and has optimal asymptotic regret but requires the engineer to tune a system-specific metaparameter.
- MAB algorithms make it easy to evaluate multiple versions—also called arms—simultaneously.
- Thompson sampling produces better business metrics during operation than epsilon-greedy and has no system-dependent metaparameter to tune.