Multi-Armed Bandits

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.13%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%3E%3D0.23.6%22%2C%0A%23%20%20%20%20%20%22numpy%3D%3D2.4.4%22%2C%0A%23%20%20%20%20%20%22pandas%3D%3D3.0.2%22%2C%0A%23%20%20%20%20%20%22plotly%3D%3D6.7.0%22%2C%0A%23%20%20%20%20%20%22torch%3D%3D2.11.0%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.23.6%22%0Aapp%20%3D%20marimo.App(%0A%20%20%20%20width%3D%22medium%22%2C%0A%20%20%20%20app_title%3D%22Multi-Armed%20Bandits%22%2C%0A%20%20%20%20css_file%3D%22%22%2C%0A%20%20%20%20auto_download%3D%5B%22html%22%5D%2C%0A)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20In%20this%20post%2C%20we%20will%20consider%20a%20subsection%20of%20RL%20called%20**Immediate%20Reinforcement%20Learning%20Problems**.%20Immediate%20RL%20involves%20agents%20receiving%20rewards%20immediately%20after%20actions%2C%20in%20contrast%20to%20to%20full%20Reinforcement%20Learning%2C%20which%20considers%20delayed%20rewards%20and%20action%20states.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20**Multi-Armed%20Bandits**%0A%20%20%20%20%23%23%23%20**%24k%24-armed%20Bandit%20problem**%0A%0A%20%20%20%20We%20have%20to%20choose%20an%20action%20repeatedly%20from%20%24k%24%20different%20actions.%20After%20each%20action%2C%20we%20are%20receive%20a%20numerical%20reward%20chosen%20from%20a%20stationary%20probability%20distribution%20that%20depends%20on%20the%20action%20selected.%20Our%20objective%20is%20to%20_maximize%20the%20expected%20total%20reward_%20over%20some%20time%20period%2C%20or%20time%20steps.%0A%0A%20%20%20%20Each%20of%20the%20%24k%24%20actions%20has%20an%20expected%20or%20mean%20reward%20given%20that%20that%20action%20is%20selected%3B%20let%20us%20call%20this%20the%20value%20of%20that%20action.%20We%20denote%20the%20action%20selected%20on%20time%20step%20%24t%24%20as%20%24A_t%24%2C%20and%20the%20corresponding%20reward%20as%20%24R_t%24.%20The%20value%20then%20of%20an%20arbitrary%20action%20%24a%24%2C%20denoted%20%24q_*(a)%24%2C%20is%20the%20expected%20reward%20given%20that%20%24a%24%20is%20selected%3A%0A%0A%20%20%20%20%24%24q_*(a)%20%5Cdoteq%20%5Cmathbb%7BE%7D%5BR_t%20%5Cmid%20A_t%20%3D%20a%5D%24%24%0A%0A%20%20%20%20Since%20we%20do%20not%20know%20the%20true%20value%20%24q_*(a)%24%20for%20each%20action%2C%20we%20would%20like%20to%20estimate%20this%20true%20value.%0A%0A%20%20%20%20We%20denote%20the%20estimated%20value%20of%20action%20%24a%24%20at%20time%20step%20%24t%24%20as%20%24Q_t(a)%24.%20Our%20goal%20then%20is%20to%20make%20%24Q_t(a)%24%20to%20be%20close%20to%20%24q_*(a)%24.%0A%0A%20%20%20%20%23%23%23%20**Action-value%20Methods**%0A%20%20%20%20The%20true%20value%20of%20an%20action%20is%20the%20mean%20reward%20when%20the%20action%20is%20selected.%20We%20can%20estimate%20this%20value%20by%20averaging%20the%20rewards%20actually%20received%3A%0A%0A%20%20%20%20%24%24Q_t(a)%20%5Cdoteq%20%5Cfrac%7B%5Csum_%7Bi%3D1%7D%5E%7Bt-1%7D%20R_i%20%5Cmathbf%7B1%7D_%7BA_i%20%3D%20a%7D%7D%7B%5Csum_%7Bi%3D1%7D%5E%7Bt-1%7D%20%5Cmathbf%7B1%7D_%7BA_i%20%3D%20a%7D%7D%24%24%0A%0A%20%20%20%20Greedy%20action%20selection%20method%3A%0A%20%20%20%20Selecting%20the%20action%20with%20the%20highest%20estimated%20value%3A%0A%20%20%20%20%24%24A_t%20%5Cdoteq%20%5Cargmax_a%7BQ_t(a)%7D%24%24%0A%0A%20%20%20%20**%24%5Cvarepsilon%24-greedy%20methods%3A**%20with%20small%20probability%20%24%5Cvarepsilon%24%2C%20select%20randomly%20from%20among%20all%20the%20actions%20with%20equal%20probability%2C%20independently%20of%20the%20action-value%20estimates.%0A%0A%20%20%20%20During%20exploration%2C%20we%20may%20select%20the%20greedy%20action%2C%20thus%20we%20have%3A%0A%20%20%20%20%24%24%0A%20%20%20%20%5CPr(a_t%20%3D%20a%5E*)%20%3D%201%20-%20%5Cvarepsilon%20%2B%20%5Cfrac%7B%5Cvarepsilon%7D%7Bk%7D%0A%20%20%20%20%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23Exercise%202.1%0A%20%20%20%20In%20%24%5Cvarepsilon%24-greedy%20action%20selection%2C%20for%20the%20case%20of%20two%20actions%20and%20%24%5Cvarepsilon%24%20%3D%200.5%2C%20what%20is%0A%20%20%20%20the%20probability%20that%20the%20greedy%20action%20is%20selected%3F%0A%0A%20%20%20%20Sol%3A%20P(greedy%20action%20chosen%20%7C%20not%20%24%5Cvarepsilon%24-greedy)%20%2B%20P(greedy%20action%20chosen%20%7C%20%24%5Cvarepsilon%24-greedy)%0A%20%20%20%20%3D%200.5x1%20%2B%200.5x0.5%20%3D%200.75%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20In%20such%20bandit%20algorithmns%2C%20we%20deal%20with%20asymptotic%20correctness%2C%20regret%20optimality%2C%20and%20PAC%20Complexity%0A%0A%20%20%20%20Correctness%20question%0A%20%20%20%20Rate%20of%20convergence%20quesiton%0A%20%20%20%20PAC%3A%20Probably%20Approximately%20Correct%0A%0A%20%20%20%20Approximately%3A%20%24q_*(a)%24%20is%20very%20close%20to%20%24q_*(a%5E*)%24%0A%20%20%20%20PAC%3A%20With%20some%20probability%20P%20your%20arm%20is%20approximately%20correct%0A%20%20%20%20%24(%5Cepsilon%2C%20%5Cdelta)%24-PAC%20%3A%20Pr%24(q_*(a)%20%5Cgeq%20q_*(a%5E*)%20-%20%5Cepsilon)%20%5Cgeq%20(1-%5Cdelta)%24%0A%0A%20%20%20%20Given%20%24%5Cepsilon%24%20and%20%24%5Cdelta%24%20what%20is%20the%20smallest%20number%20of%20times%20we%20have%20to%20draw%20an%20arm%20to%20guarantee%20PAC%20optimality%3F%0A%20%20%20%20This%20is%20a%20sample%20complexity%20question%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20**The%2010-armed%20Testbed**%0A%20%20%20%20This%20is%20a%20set%20of%202000%20randomly%20generated%20%24k%24-armed%20bandit%20problems%2C%20with%20%24k%3D10%24.%20For%20each%20bandit%20problem%2C%20the%20action%20values%2C%20%24q_*(a)%2C%20a%20%3D%201%2C%20.%20.%20.%20%2C%2010%24%2C%20were%20selected%20according%20to%20a%20normal%20(Gaussian)%20distribution%20with%20mean%200%20and%20variance%201.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20plotly.express%20as%20px%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20torch%0A%0A%20%20%20%20return%20np%2C%20pd%2C%20px%2C%20torch%0A%0A%0A%40app.cell%0Adef%20_(torch)%3A%0A%20%20%20%20class%20Bandit%3A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20k%3D10)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.k%20%3D%20k%0A%20%20%20%20%20%20%20%20%20%20%20%20self.qs%20%3D%20torch.randn(k)%0A%0A%20%20%20%20%20%20%20%20def%20act(self%2C%20k)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20r%20%3D%20self.qs%5Bk%5D%20%2B%20torch.randn(1)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20r.item()%0A%0A%20%20%20%20return%20(Bandit%2C)%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20torch)%3A%0A%20%20%20%20n%20%3D%202000%0A%20%20%20%20k%20%3D%2010%0A%20%20%20%20R%20%3D%20torch.zeros((n%2Ck))%0A%20%20%20%20b%20%3D%20Bandit(k)%0A%20%20%20%20for%20i%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(k)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bi%2Cj%5D%20%3D%20b.act(j)%0A%20%20%20%20return%20R%2C%20b%2C%20k%0A%0A%0A%40app.cell%0Adef%20_(R%2C%20b%2C%20k%2C%20mo%2C%20pd%2C%20px)%3A%0A%20%20%20%20%23%20Convert%20to%20long-form%20DataFrame%20for%20plotly%0A%20%20%20%20df%20%3D%20pd.DataFrame(R.numpy()%2C%20columns%3D%5Bf%22Action%20%7Bj%2B1%7D%22%20for%20j%20in%20range(k)%5D)%0A%20%20%20%20df_long%20%3D%20df.melt(var_name%3D%22Action%22%2C%20value_name%3D%22Reward%22)%0A%0A%20%20%20%20_fig%20%3D%20px.violin(%0A%20%20%20%20%20%20%20%20df_long%2C%0A%20%20%20%20%20%20%20%20x%3D%22Action%22%2C%0A%20%20%20%20%20%20%20%20y%3D%22Reward%22%2C%0A%20%20%20%20%20%20%20%20box%3DTrue%2C%0A%20%20%20%20%20%20%20%20points%3DFalse%2C%0A%20%20%20%20%20%20%20%20title%3D%22Reward%20Distributions%20for%20Each%20Action%20(k-Armed%20Bandit)%22%2C%0A%20%20%20%20%20%20%20%20color%3D%22Action%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Overlay%20the%20true%20q*(a)%20values%20as%20scatter%20points%0A%20%20%20%20_fig.add_scatter(%0A%20%20%20%20%20%20%20%20x%3D%5Bf%22Action%20%7Bj%2B1%7D%22%20for%20j%20in%20range(k)%5D%2C%0A%20%20%20%20%20%20%20%20y%3Db.qs.numpy()%2C%0A%20%20%20%20%20%20%20%20mode%3D%22markers%22%2C%0A%20%20%20%20%20%20%20%20marker%3Ddict(symbol%3D%22star%22%2C%20size%3D10%2C%20color%3D%22black%22)%2C%0A%20%20%20%20%20%20%20%20name%3D%22q*(a)%20true%20value%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20plot%20%3D%20mo.ui.plotly(_fig)%0A%20%20%20%20plot%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23%20Naive%20Algorithm%0A%20%20%20%20We%20compare%20a%20greedy%20method%20with%20two%20%24%5Cvarepsilon%24-greedy%20methods%20(%24%5Cvarepsilon%24%20%3D%200.01%20and%20%24%5Cvarepsilon%24%20%3D%200.1)%20on%20the%2010-armed%20testbed.%20All%20the%20methods%20formed%20their%20action-value%20estimates%20using%20the%20sample-average%20technique.%20The%20upper%20graph%20shows%20the%20increase%20in%20expected%20reward%20with%20experience.%20These%20data%20are%20averages%20over%202000%20runs%20with%20different%20bandit%20problems%20across%201000%20time-steps.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20torch)%3A%0A%20%20%20%20def%20naive_algorithm(b%3A%20Bandit%2C%20eps%3A%20float%2C%20n%3A%20int%20%3D%201000)%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20S%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20Q%20%3D%20torch.zeros(b.k)%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20torch.rand(1).item()%20%3C%20eps%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.randint(0%2C%20b.k%2C%20(1%2C)).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.argmax(Q%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20N%5BA_t%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20S%5BA_t%5D%20%2B%3D%20R_t%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%5BA_t%5D%20%3D%20S%5BA_t%5D%20%2F%20N%5BA_t%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20for%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(naive_algorithm%2C)%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20mo%2C%20pd%2C%20px%2C%20torch)%3A%0A%20%20%20%20def%20run_bandit_experiment(algo_fn%3DNone%2C%20algo_name%3D%22%22%2C%20k%3D10%2C%20configs%3D()%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20n_runs%3D2000%2C%20n_steps%3D1000%2C%20bandit_fn%3DBandit)%3A%0A%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20algo_fn%3A%20%20%20callable(bandit%2C%20n%3Dn_steps%2C%20**kwargs)%20-%3E%20(Q%2C%20R%2C%20Qopt)%0A%20%20%20%20%20%20%20%20%20%20bandit_fn%3A%20callable(k)%20-%3E%20fresh%20bandit%20instance.%20Defaults%20to%20Bandit%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pass%20a%20factory%20for%20NonStationaryBandit%20(see%20below).%0A%20%20%20%20%20%20%20%20%20%20configs%3A%20%20%20list%20of%20dicts%2C%20each%20with%20a%20%22label%22%3B%20other%20keys%20-%3E%20algo_fn%20kwargs.%0A%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20%20%20avg_ravg%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20%20%20avg_qopt%20%3D%20%7B%7D%0A%0A%20%20%20%20%20%20%20%20%20%20for%20cfg%20in%20configs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%20%3D%20cfg%5B%22label%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20fn%20%3D%20cfg.get(%22algo_fn%22%2C%20algo_fn)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20per-config%20algo%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20kwargs%20%3D%20%7Bkey%3A%20val%20for%20key%2C%20val%20in%20cfg.items()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20key%20not%20in%20(%22label%22%2C%20%22algo_fn%22)%7D%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20exclude%20both%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20run_ravg%20%3D%20torch.zeros((n_runs%2C%20n_steps))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20run_qopt%20%3D%20torch.zeros((n_runs%2C%20n_steps))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20run_idx%20in%20range(n_runs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bandit%20%3D%20bandit_fn(k)%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_%2C%20Ravg%2C%20Qopt%20%3D%20fn(bandit%2C%20n%3Dn_steps%2C%20**kwargs)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20run_ravg%5Brun_idx%5D%20%3D%20Ravg%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20run_qopt%5Brun_idx%5D%20%3D%20Qopt%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20avg_ravg%5Blabel%5D%20%3D%20run_ravg.mean(dim%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20avg_qopt%5Blabel%5D%20%3D%20run_qopt.mean(dim%3D0)%0A%0A%20%20%20%20%20%20%20%20%20%20df_ravg%20%3D%20pd.DataFrame(%7Blabel%3A%20v.numpy()%20for%20label%2C%20v%20in%20avg_ravg.items()%7D)%0A%20%20%20%20%20%20%20%20%20%20df_ravg%5B%22Step%22%5D%20%3D%20range(n_steps)%0A%20%20%20%20%20%20%20%20%20%20df_ravg_melted%20%3D%20df_ravg.melt(id_vars%3D%22Step%22%2C%20var_name%3D%22Policy%22%2C%20value_name%3D%22Ravg%22)%0A%20%20%20%20%20%20%20%20%20%20fig_ravg%20%3D%20px.line(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20df_ravg_melted%2C%20x%3D%22Step%22%2C%20y%3D%22Ravg%22%2C%20color%3D%22Policy%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20title%3Df%22Average%20Reward%20over%20Time%20(%7Balgo_name%7D%2C%20%7Bn_runs%7D%20runs)%22%2C%0A%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20df_qopt%20%3D%20pd.DataFrame(%7Blabel%3A%20v.numpy()%20for%20label%2C%20v%20in%20avg_qopt.items()%7D)%0A%20%20%20%20%20%20%20%20%20%20df_qopt%5B%22Step%22%5D%20%3D%20range(n_steps)%0A%20%20%20%20%20%20%20%20%20%20df_qopt_melted%20%3D%20df_qopt.melt(id_vars%3D%22Step%22%2C%20var_name%3D%22Policy%22%2C%20value_name%3D%22Optimal%20Action%20%25%22)%0A%20%20%20%20%20%20%20%20%20%20fig_qopt%20%3D%20px.line(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20df_qopt_melted%2C%20x%3D%22Step%22%2C%20y%3D%22Optimal%20Action%20%25%22%2C%20color%3D%22Policy%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20title%3Df%22Optimal%20Action%20%25%20over%20Time%20(%7Balgo_name%7D%2C%20%7Bn_runs%7D%20runs)%22%2C%0A%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20fig_qopt.update_yaxes(tickformat%3D%22.0%25%22)%0A%0A%20%20%20%20%20%20%20%20%20%20return%20mo.vstack(%5Bmo.ui.plotly(fig_ravg)%2C%20mo.ui.plotly(fig_qopt)%5D)%0A%0A%20%20%20%20return%20(run_bandit_experiment%2C)%0A%0A%0A%40app.cell%0Adef%20_(k%2C%20naive_algorithm%2C%20run_bandit_experiment)%3A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20%20%20algo_fn%3Dnaive_algorithm%2C%0A%20%20%20%20%20%20%20%20algo_name%3D%22Naive%20%CE%B5-Greedy%22%2C%0A%20%20%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20%20%20configs%3D%5B%7B%22label%22%3A%20f%22%CE%B5%3D%7Be%7D%22%2C%20%22eps%22%3A%20e%7D%20for%20e%20in%20%5B0.0%2C%200.01%2C%200.1%5D%5D%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23%20Incremental%20Implementation%0A%20%20%20%20In%20the%20previous%20implementation%2C%20we%20estimate%20action%20values%20as%20sample%20averages%20of%20observed%20rewards.%20We%20can%20create%20a%20more%20computationally%20efficient%20implementation%20with%20constant%20memory%20and%20per-time-step%20computations.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Let%20us%20consider%20only%20a%20single%20action.%20Let%20%24R_i%24%20denote%20the%20reward%20received%20after%20the%20%24i%24th%20selection%20of%20_this%20action_%2C%20and%20let%20%24Q_n%24%20denote%20the%20estimate%20of%20this%20action's%20value%20after%20it%20has%20been%20selected%20%24n-1%24%20times.%0A%20%20%20%20%24%24%0A%20%20%20%20Q_n%20%5Cdoteq%20%5Cfrac%7BR_1%20%2B%20R_2%20%2B%20...%20%2B%20R_%7Bn-1%7D%7D%7Bn-1%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20We%20can%20incrementally%20compute%20this%20by%3A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20Q_n%20%26%3D%20%5Cfrac%7B1%7D%7Bn%7D%20%5Csum_%7Bi%3D1%7D%5E%7Bn%7DR_i%20%5C%5C%0A%20%20%20%20%26%3D%20%5Cfrac%7B1%7D%7Bn%7D%20%5Cleft(%20R_n%20%2B%20%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7DR_i%20%5Cright)%20%5C%5C%0A%20%20%20%20%26%3D%20%5Cfrac%7B1%7D%7Bn%7D%20%5Cleft(%20R_n%20%2B%20(n-1)%20%5Cfrac%7B1%7D%7Bn-1%7D%20%5Csum_%7Bi%3D1%7D%5E%7Bn-1%7DR_i%20%5Cright)%20%5C%5C%0A%20%20%20%20%26%3D%20%5Cfrac%7B1%7D%7Bn%7D%20%5Cleft(%20R_n%20%2B%20(n-1)Q_%7Bn-1%7D%20%5Cright)%20%5C%5C%0A%20%20%20%20%26%3D%20%5Cfrac%7B1%7D%7Bn%7D%20%5Cleft(%20R_n%20%2B%20nQ_%7Bn-1%7D%20-%20Q_%7Bn-1%7D%20%5Cright)%20%5C%5C%0A%20%20%20%20%26%3D%20%5Cfrac%7B1%7D%7Bn%7D%20%5Cleft(%20nQ_%7Bn-1%7D%20%2B%20R_n%20-%20Q_%7Bn-1%7D%20%5Cright)%20%5C%5C%0A%20%20%20%20%26%3D%20Q_%7Bn-1%7D%20%2B%20%5Cfrac%7B1%7D%7Bn%7D%20%5BR_n%20-%20Q_%7Bn-1%7D%5D%0A%20%20%20%20%5Cend%7Baligned%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20This%20gives%20us%20a%20general%20update%20rule%20which%20is%20as%20follows%3A%0A%0A%20%20%20%20%24NewEstimate%20%5Cleftarrow%20OldEstimate%20%2B%20StepSize%5BTarget%20-%20OldEstimate%5D%24%0A%0A%20%20%20%20This%20is%20a%20form%20of%20a%20general%20class%20of%20equations%20called%20_Stochastic%20Averaging%20Equations_%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20torch)%3A%0A%20%20%20%20def%20simple_algorithm(b%3A%20Bandit%2C%20eps%3A%20float%2C%20n%3A%20int%20%3D%201000)%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20Q%20%3D%20torch.zeros(b.k)%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20torch.rand(1).item()%20%3C%20eps%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.randint(0%2C%20b.k%2C%20(1%2C)).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.argmax(Q%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20N%5BA_t%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%5BA_t%5D%20%2B%3D%20(R_t%20-%20Q%5BA_t%5D)%2FN%5BA_t%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(simple_algorithm%2C)%0A%0A%0A%40app.cell%0Adef%20_(k%2C%20run_bandit_experiment%2C%20simple_algorithm)%3A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20%20%20algo_fn%3Dsimple_algorithm%2C%0A%20%20%20%20%20%20%20%20algo_name%3D%22Simple%20%CE%B5-Greedy%22%2C%0A%20%20%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20%20%20configs%3D%5B%7B%22label%22%3A%20f%22%CE%B5%3D%7Be%7D%22%2C%20%22eps%22%3A%20e%7D%20for%20e%20in%20%5B0.0%2C%200.01%2C%200.1%5D%5D%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%23%20**Alternate%20strategies**%0A%0A%20%20%20%20%23%23%23%23%20%24%5Cvarepsilon%24-decreasing%20strategy%0A%0A%20%20%20%20Initially%2C%20our%20estimate%20of%20the%20true%20rewards%20are%20far%20from%20the%20true%20values%2C%20thus%20exploitation%20is%20not%20a%20good%20strategy%20to%20begin%20with.%20In%20this%20strategy%20we%20begin%20with%20a%20high%20value%20of%20%24%5Cvarepsilon%24%20to%20encourage%20more%20exploration%2C%20and%20gradually%20decrease%20it%20and%20exploit%20more%20as%20we%20gather%20more%20data.%0A%0A%20%20%20%20For%20this%2C%20we%20introduce%20a%20new%20parameter%20%24%5Calpha%20%5Cin%20%5B0%2C1%5D%24%2C%20called%20_decay_%2C%20which%20is%20used%20to%20decrease%20%24%5Cvarepsilon%24%20over%20time.%20We%20decay%20%24%5Cvarepsilon%24%20using%20%24%5Cvarepsilon%20%3D%20%5Cvarepsilon%20%5Ccdot%20%5Calpha%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20torch)%3A%0A%20%20%20%20def%20epsilon_decreasing(b%3A%20Bandit%2C%20eps%3A%20float%20%3D%201.0%2C%20alpha%3A%20float%20%3D%200.9%2C%20n%3A%20int%20%3D%201000)%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20Q%20%3D%20torch.zeros(b.k)%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20torch.rand(1).item()%20%3C%20eps%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.randint(0%2C%20b.k%2C%20(1%2C)).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.argmax(Q%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20N%5BA_t%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%5BA_t%5D%20%2B%3D%20(R_t%20-%20Q%5BA_t%5D)%2FN%5BA_t%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20decay%20epsilon%0A%20%20%20%20%20%20%20%20%20%20%20%20eps%20%3D%20eps%20*%20alpha%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(epsilon_decreasing%2C)%0A%0A%0A%40app.cell%0Adef%20_(epsilon_decreasing%2C%20k%2C%20run_bandit_experiment)%3A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20%20%20algo_fn%3Depsilon_decreasing%2C%0A%20%20%20%20%20%20%20%20algo_name%3D%22%CE%B5-Decreasing%22%2C%0A%20%20%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20%20%20configs%3D%5B%7B%22label%22%3A%20f%22%CE%B5%E2%82%80%3D1.0%2C%20%CE%B1%3D%7Ba%7D%22%2C%20%22eps%22%3A%201.0%2C%20%22alpha%22%3A%20a%7D%20for%20a%20in%20%5B0.9%2C%200.99%2C%200.999%5D%5D%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23%20Softmax%20strategy%0A%20%20%20%20Instead%20of%20uniformly%20selecting%20the%20actions%2C%20since%20we%20already%20have%20an%20estimate%20of%20their%20true%20values%2C%20this%20strategy%20enables%20us%20to%20select%20actions%20depending%20on%20their%20%24Q%24-values.%20We%20choose%20actions%20from%20the%20Gibbs%2C%20or%20Boltzmann%20distribution%3A%0A%20%20%20%20%24%24%0A%20%20%20%20Pr(a_t%20%3D%20a)%20%3D%20%5Cfrac%7Be%5E%7BQ(a)%2F%5Ctau%7D%7D%7B%5Csum%5E%7Bk%7D_%7Bb%3D1%7De%5E%7BQ(b)%2F%5Ctau%7D%7D%0A%20%20%20%20%24%24%0A%20%20%20%20Where%20%24%5Ctau%24%20is%20a%20positive%20parameter%20called%20_temperature_.%20High%20temperature%20values%20cause%20the%20action%20selection%20to%20be%20equiprobable%2C%20and%20lower%20values%20make%20the%20selection%20more%20selective.%20As%20%24%5Ctau%20%5Crightarrow%200%24%2C%20the%20softmax%20strategy%20becomes%20the%20same%20as%20greedy%20selection.%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20**Note%3A**%20How%20to%20pick%20from%20a%20probability%20distribution%0A%20%20%20%20To%20implement%20the%20softmax%20strategy%2C%20we%20somehow%20have%20to%20pick%20a%20value%20from%20a%20given%20probability%20distribution%2C%20which%20may%20not%20have%20a%20direct%20implementation%20(such%20as%20randn).%20In%20our%20case%2C%20our%20softmax%20function%20returns%20a%20list%20of%20probabilities%20for%20each%20action%2C%20with%20the%20sum%20of%20individual%20probabilities%20equalling%201.%0A%0A%20%20%20%20Let%20us%20assume%20we%20have%20a%20list%20of%20probabilities%20to%20choose%20from%204%20actions%3A%20%24%5Bp_1%2C%20p_2%2C%20p_3%2C%20p_4%5D%24%0A%0A%20%20%20%20To%20then%20sample%20from%20these%20probabilities%20we%20do%20the%20following%3A%0A%20%20%20%20-%20Pick%20a%20random%20number%20%24n%24%20uniformly%20from%20%5B0%2C1%5D%0A%20%20%20%20-%20If%20%24n%20%5Cin%20%5B0%2C%20p_1%5D%24%2C%20choose%20action%201%0A%20%20%20%20-%20If%20%24n%20%5Cin%20%5Bp_1%2C%20p_1%20%2B%20p_2%5D%24%2C%20choose%20action%202%0A%20%20%20%20-%20If%20%24n%20%5Cin%20%5Bp_1%20%2B%20p_2%2C%20p_1%20%2B%20p_2%20%2B%20p_3%5D%24%2C%20choose%20action%203%0A%20%20%20%20-%20If%20%24n%20%5Cin%20%5Bp_1%20%2B%20p_2%20%2B%20p_3%2C%201%5D%24%2C%20choose%20action%204%0A%0A%20%20%20%20And%20we%20can%20generalize%20this%20method%20for%20any%20number%20of%20actions.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20torch)%3A%0A%20%20%20%20def%20softmax(x%3A%20torch.Tensor%2C%20dim%3A%20int%20%3D%20-1)%20-%3E%20torch.Tensor%3A%0A%20%20%20%20%20%20%20%20%23%20subtract%20max%20value%20for%20numerical%20stability%0A%20%20%20%20%20%20%20%20x_max%20%3D%20torch.max(x%2C%20dim%3Ddim%2C%20keepdim%3DTrue).values%0A%20%20%20%20%20%20%20%20return%20torch.exp(x-x_max)%20%2F%20torch.sum(torch.exp(x-x_max)%2C%20dim%3Ddim%2C%20keepdim%3DTrue)%0A%0A%20%20%20%20def%20pick_action(p%3A%20torch.Tensor)%20-%3E%20int%3A%0A%20%20%20%20%20%20%20%20n%20%3D%20torch.rand(1).item()%0A%20%20%20%20%20%20%20%20hi%20%3D%200.0%0A%20%20%20%20%20%20%20%20for%20i%2C%20pi%20in%20enumerate(p.tolist())%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20lo%20%3D%20hi%0A%20%20%20%20%20%20%20%20%20%20%20%20hi%20%2B%3D%20pi%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20lo%20%3C%3D%20n%20%3C%20hi%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20i%0A%20%20%20%20%20%20%20%20return%20len(p)-1%0A%0A%20%20%20%20def%20softmax_algorithm(b%3A%20Bandit%2C%20tau%3A%20float%20%3D%201.0%2C%20alpha%3A%20float%20%3D%200.99%2C%20n%3A%20int%20%3D%201000)%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20Q%20%3D%20torch.zeros(b.k)%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20create%20softmax%20distribution%20of%20current%20estimate%20and%20pick%20action%0A%20%20%20%20%20%20%20%20%20%20%20%20Q_softmax%20%3D%20softmax(Q%20%2F%20tau)%0A%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20pick_action(Q_softmax)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20N%5BA_t%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%5BA_t%5D%20%2B%3D%20(R_t%20-%20Q%5BA_t%5D)%2FN%5BA_t%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20decay%20temperature%0A%20%20%20%20%20%20%20%20%20%20%20%20tau%20%3D%20tau%20*%20alpha%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(softmax_algorithm%2C)%0A%0A%0A%40app.cell%0Adef%20_(k%2C%20run_bandit_experiment%2C%20softmax_algorithm)%3A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20%20%20algo_fn%3Dsoftmax_algorithm%2C%0A%20%20%20%20%20%20%20%20algo_name%3D%22Softmax%22%2C%0A%20%20%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20%20%20configs%3D%5B%7B%22label%22%3A%20f%22%CF%84%3D%7Bt%7D%22%2C%20%22tau%22%3A%20t%7D%20for%20t%20in%20%5B10.0%2C%201.0%2C%200.1%2C%200.01%5D%5D%2C%0A%20%20%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23Exercise%202.3%0A%20%20%20%20Show%20that%20in%20the%20case%20of%20two%20actions%2C%20the%20softmax%20operation%20using%20the%20Gibbs%20distribution%20becomes%20the%20logistic%2C%20or%20sigmoid%2C%20function%20commonly%20used%20in%20artificial%20neural%20networks.%20What%20effect%20does%20the%20temperature%20parameter%20have%20on%20the%20function%3F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20If%20we%20only%20have%20two%20actions%3A%0A%20%20%20%20%24%5C%7Ba_1%2C%20a_2%5C%7D%24%0A%20%20%20%20%24%24%0A%20%20%20%20Pr(a_1)%20%3D%20%5Cfrac%7Be%5E%7BQ(a_1)%2F%5Ctau%7D%7D%7Be%5E%7BQ(a_1)%2F%5Ctau%7D%20%2B%20e%5E%7BQ(a_2)%2F%5Ctau%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B1%2Be%5E%7B(Q(a_%7B2%7D)%20-%20Q(a_1))%2F%5Ctau%7D%7D%0A%20%20%20%20%5C%5C%0A%20%20%20%20%3D%20%5Cfrac%7B1%7D%7B1%2Be%5E%7B-x%7D%7D%0A%20%20%20%20%24%24%0A%20%20%20%20where%0A%20%20%20%20%24%24%0A%20%20%20%20x%20%3D%20%5Cfrac%7BQ(a_%7B1%7D)%20-%20Q(a_2)%7D%7B%5Ctau%7D%0A%20%20%20%20%24%24%0A%20%20%20%20This%20is%20equivalent%20to%20the%20sigmoid%20function%20%24%5Csigma(x)%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20**Tracking%20non-stationary%20problems**%0A%0A%20%20%20%20In%20the%20real%20world%2C%20we%20typically%20encounter%20reinforcement%20learning%20problems%20that%20are%20effectively%20non-stationary.%20In%20such%20cases%2C%20it%20makes%20more%20sense%20to%20weight%20more%20recent%20rewards%20higher%20than%20long-past%20rewards.%20We%20can%20update%20the%20incremental%20update%20rule%20to%20be%3A%0A%20%20%20%20%24%24%0A%20%20%20%20Q_%7Bn%2B1%7D%20%5Cdoteq%20Q_n%20%2B%20%5Calpha%5BR_n%20-%20Q_n%5D%0A%20%20%20%20%24%24%0A%20%20%20%20where%20the%20step%20size%20parameter%20%24%5Calpha%20%5Cin%20(0%2C1%5D%24%20is%20constant.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20torch)%3A%0A%20%20%20%20class%20NonStationaryBandit(Bandit)%3A%0A%20%20%20%20%20%20%20%20def%20equalize(self%2C%20q)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.qs%20%3D%20torch.ones(self.k)%20*%20q%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%0A%20%20%20%20%20%20%20%20def%20move_all(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20walks%20%3D%20torch.normal(mean%3D0%2C%20std%3D0.01%2C%20size%3Dself.qs.shape)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.qs%20%2B%3D%20walks%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%0A%20%20%20%20return%20(NonStationaryBandit%2C)%0A%0A%0A%40app.cell%0Adef%20_(NonStationaryBandit%2C%20torch)%3A%0A%20%20%20%20def%20nsb_sample_avg(b%3A%20NonStationaryBandit%2C%20eps%3A%20float%20%3D%200.1%2C%20n%3A%20int%20%3D%2010000)%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20Q%20%3D%20torch.zeros(b.k)%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20torch.rand(1).item()%20%3C%20eps%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.randint(0%2C%20b.k%2C%20(1%2C)).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.argmax(Q%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20N%5BA_t%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%5BA_t%5D%20%2B%3D%20(R_t%20-%20Q%5BA_t%5D)%2FN%5BA_t%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20take%20random%20step%20for%20bandit%0A%20%20%20%20%20%20%20%20%20%20%20%20b.move_all()%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(nsb_sample_avg%2C)%0A%0A%0A%40app.cell%0Adef%20_(NonStationaryBandit%2C%20k%2C%20nsb_sample_avg%2C%20run_bandit_experiment)%3A%0A%20%20%20%20def%20make_ns_bandit(k)%3A%0A%20%20%20%20%20%20b%20%3D%20NonStationaryBandit(k)%0A%20%20%20%20%20%20b.equalize(0.0)%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20return%20b%0A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20algo_fn%3Dnsb_sample_avg%2C%0A%20%20%20%20%20%20algo_name%3D%22Non-stationary%20(incremental)%22%2C%0A%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20configs%3D%5B%7B%22label%22%3A%20f%22%CE%B5%3D%7Be%7D%22%2C%20%22eps%22%3A%20e%7D%20for%20e%20in%20%5B0.0%2C%200.01%2C%200.1%5D%5D%2C%0A%20%20%20%20%20%20n_runs%3D200%2C%0A%20%20%20%20%20%20n_steps%3D10000%2C%0A%20%20%20%20%20%20bandit_fn%3Dmake_ns_bandit%2C%0A%20%20%20%20)%0A%20%20%20%20return%20(make_ns_bandit%2C)%0A%0A%0A%40app.cell%0Adef%20_(NonStationaryBandit%2C%20torch)%3A%0A%20%20%20%20def%20nsb_av_steps(b%3A%20NonStationaryBandit%2C%20eps%3A%20float%20%3D%200.1%2C%20alpha%3A%20float%20%3D%200.1%2C%20n%3A%20int%20%3D%2010000)%3A%0A%20%20%20%20%20%20%20%20Q%20%3D%20torch.zeros(b.k)%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20torch.rand(1).item()%20%3C%20eps%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.randint(0%2C%20b.k%2C%20(1%2C)).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.argmax(Q%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20recency%20weighted%20avg%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%5BA_t%5D%20%2B%3D%20(R_t%20-%20Q%5BA_t%5D)%20*%20alpha%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20take%20random%20step%20for%20bandit%0A%20%20%20%20%20%20%20%20%20%20%20%20b.move_all()%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(nsb_av_steps%2C)%0A%0A%0A%40app.cell%0Adef%20_(k%2C%20make_ns_bandit%2C%20nsb_av_steps%2C%20run_bandit_experiment)%3A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20algo_fn%3Dnsb_av_steps%2C%0A%20%20%20%20%20%20algo_name%3D%22Non-stationary%20(constant-%CE%B1)%22%2C%0A%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20configs%3D%5B%7B%22label%22%3A%20f%22%CE%B5%3D%7Be%7D%2C%20%CE%B1%3D0.1%22%2C%20%22eps%22%3A%20e%2C%20%22alpha%22%3A%200.1%7D%20for%20e%20in%20%5B0.1%5D%5D%2C%0A%20%20%20%20%20%20n_runs%3D200%2C%0A%20%20%20%20%20%20n_steps%3D10000%2C%0A%20%20%20%20%20%20bandit_fn%3Dmake_ns_bandit%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23%20Optimistic%20Initial%20Values%0A%20%20%20%20methods%20are%20biased%20by%20their%20initial%20estimates.%20For%20the%20sample-average%20methods%2C%20the%20bias%20disappears%20once%20all%0A%20%20%20%20actions%20have%20been%20selected%20at%20least%20once%2C%20but%20for%20methods%20with%20constant%20%E2%86%B5%2C%20the%20bias%20is%0A%20%20%20%20permanent%2C%20though%20decreasing%20over%20time%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20torch)%3A%0A%20%20%20%20def%20optimistic_initial(b%3A%20Bandit%2C%20q%3A%20float%20%3D%205%2C%20n%3A%20int%20%3D%201000)%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20Q%20%3D%20q*torch.ones(b.k)%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.argmax(Q%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20N%5BA_t%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%5BA_t%5D%20%2B%3D%20(R_t%20-%20Q%5BA_t%5D)%2FN%5BA_t%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(optimistic_initial%2C)%0A%0A%0A%40app.cell%0Adef%20_(k%2C%20optimistic_initial%2C%20run_bandit_experiment%2C%20simple_algorithm)%3A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20%20%20%20%20algo_name%3D%22Optimistic%20Initial%20Values%20vs%20%CE%B5-greedy%22%2C%0A%20%20%20%20%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20%20%20%20%20configs%3D%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22label%22%3A%20%22Optimistic%20Initial%20Values%20(Q_1%3D5)%22%2C%20%22algo_fn%22%3A%20optimistic_initial%2C%20%22q%22%3A%205.0%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22label%22%3A%20%22%CE%B5-greedy%200.1%22%2C%20%22algo_fn%22%3A%20simple_algorithm%2C%20%22eps%22%3A%200.1%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20**Upper%20Confidence%20Bound%20(UCB1)%20Algorithm**%0A%20%20%20%20Assume%20there%20are%20%24K%24%20arms%2C%20and%20with%20each%20arm%20there%20is%20an%20associated%20reward%20probability%20distribution.%20Let%20us%20assume%20this%20distribution%20is%20stationary.%0A%0A%20%20%20%20**Initialization%3A**%20Play%20each%20arm%20once%0A%0A%20%20%20%20**Loop**%0A%20%20%20%20-%20Play%20arm%20%24j%24%20that%20maximizes%20%24Q(j)%20%2B%20%5Csqrt%7B%5Cfrac%7B2%5Cln%20n%7D%7Bn_j%7D%7D%24%0A%0A%20%20%20%20Where%20%24n_j%24%20is%20the%20number%20of%20times%20arm%20%24j%24%20has%20been%20played.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20Theorem%0A%20%20%20%20For%20all%20%24K%20%3E%201%24%2C%20if%20UCB1%20is%20run%20on%20%24K%24%20arms%20having%20arbitrary%20reward%20distributions%2C%20with%20support%20in%20%24%5B0%2C1%5D%24%2C%20then%20its%20expected%20regret%20after%20any%20number%20of%20plays%20%24n%24%20is%20at%20most%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cleft%5B8%5Csum_%7Bi%3Aq_*(i)%20%3C%20q_*(a%5E*)%7D%20%5Cleft(%20%5Cfrac%7B%5Cln%20n%7D%7B%5CDelta_i%7D%20%5Cright)%5Cright%5D%20%2B%20%5Cleft(1%20%2B%20%5Cfrac%7B%5Cpi%5E2%7D%7B3%7D%5Cright)%5Cleft(%5Csum_%7Bj%7D%5E%7BK%7D%5CDelta_j%5Cright)%0A%20%20%20%20%5C%5C%0A%20%20%20%20%5Ctext%7Bwhere%2C%20%7D%5CDelta_i%20%3D%20q_*(a%5E*)%20-%20q_*(i)%0A%20%20%20%20%24%24%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23%20Proof%0A%20%20%20%20_Source%3A%20%5BAuer%2C%20Cesa-Bianchi%20%26%20Fischer%20(2002)%2C%20%22Finite-time%20Analysis%20of%20the%20Multiarmed%20Bandit%0A%20%20%20%20Problem%22%5D(https%3A%2F%2Fhomes.di.unimi.it%2F~cesabian%2FPubblicazioni%2Fml-02.pdf)_%0A%0A%20%20%20%20Let%20us%20introduce%20some%20terms%3A%0A%0A%20%20%20%20%24T_i(n)%24%3A%20No.%20of%20times%20arm%20i%20played%20in%20n%20trials%0A%0A%20%20%20%20Regret%24_n%24%20%3D%20%24%5Csum_%7Bi%7D%20E%5BT_i(n)%5D%5CDelta_i%24%0A%0A%20%20%20%20%24X_%7Bi%2Cn%7D%24%3A%20Reward%20obtained%20for%20playing%20action%20i%20at%20time%20n%20(random%20variable)%0A%0A%20%20%20%20%24E%5BX_%7Bi%2Cn%7D%5D%20%3D%20q_*(i)%24%0A%0A%20%20%20%20We%20show%20that%20%3A%0A%20%20%20%20%24%24%0A%20%20%20%20E%5BT_j(n)%5D%20%5Cleq%20%5Cfrac%7B8%7D%7B%5CDelta_j%5E2%7D%20%5Cln%20n%20%2B%20c%0A%20%20%20%20%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20**Chernoff-Hoeffding%20Bound**%0A%0A%20%20%20%20Let%20%24X_1%2C%20...%2C%20X_n%24%20be%20r.v.%20with%20common%20range%20%24%5B0%2C1%5D%24%20and%20such%20that%20%24%5Cmathbb%7BE%7D%5BX_t%7CX_1%2C%20...%2C%20X_%7Bt-1%7D%5D%20%3D%20%5Cmu%24.%20Let%20%24S_n%20%3D%20%5Cfrac%7BX_1%20%2B%20...%20%2B%20X_n%7D%7Bn%7D%24.%0A%20%20%20%20Then%20for%20all%20%24a%20%5Cgeq%200%24%3A%0A%20%20%20%20%24%24%0A%20%20%20%20Pr(S_n%20%5Cgeq%20%5Cmu%20%2B%20%5Cepsilon)%20%5Cleq%20e%5E%7B-2%20%5Cepsilon%5E2n%7D%0A%20%20%20%20%24%24%0A%20%20%20%20and%0A%20%20%20%20%24%24%0A%20%20%20%20Pr(S_n%20%5Cleq%20%5Cmu%20-%20%5Cepsilon)%20%5Cleq%20e%5E%7B-2%20%5Cepsilon%5E2n%7D%0A%20%20%20%20%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Let%20%24C_%7Bn%2Cs%7D%20%3D%20%5Csqrt%7B%5Cdfrac%7B2%5Cln%20n%7D%7Bs%7D%7D%24%20be%20our%20confidence-bound%20function.%0A%0A%20%20%20%20Let%20us%20introduce%20the%20indicator%20%24%5C%7BI_n%20%3D%20i%5C%7D%24%2C%20a%20random%20variable%20whose%20value%20is%20%241%24%20if%20at%0A%20%20%20%20time%20%24n%24%20the%20arm%20chosen%20is%20arm%20%24i%24%2C%20and%20%240%24%20otherwise.%20Let%20%24l%24%20be%20an%20arbitrary%20positive%0A%20%20%20%20integer.%20Now%20we%20have%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20T_i(n)%0A%20%20%20%20%26%3D%201%20%2B%20%5Csum_%7Bm%3DK%2B1%7D%5E%7Bn%7D%20%5C%7BI_m%20%3D%20i%5C%7D%0A%20%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B(number%20of%20times%20we%20pull%20arm%20%7D%20i%5Ctext%7B)%7D%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20%26%5Cleq%20l%20%2B%20%5Csum_%7Bm%3DK%2B1%7D%5E%7Bn%7D%20%5C%7BI_m%20%3D%20i%2C%5C%3B%20T_i(m-1)%20%5Cgeq%20l%5C%7D%0A%20%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B(count%20only%20after%20%7D%20l%20%5Ctext%7B%20pulls)%7D%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20%26%5Cleq%20l%20%2B%20%5Csum_%7Bm%3DK%2B1%7D%5E%7Bn%7D%5Cleft%5C%7B%20Q(a%5E*)%20%2B%20C_%7Bm-1%2C%5C%2CT_%7Ba%5E*%7D(m-1)%7D%20%5Cleq%20Q(i)%20%2B%20C_%7Bm-1%2C%5C%2CT_i(m-1)%7D%2C%5C%3B%20T_i(m-1)%20%5Cgeq%20l%20%5Cright%5C%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20%26%5Cleq%20l%20%2B%20%5Csum_%7Bm%3DK%2B1%7D%5E%7Bn%7D%5Cleft%5C%7B%20%5Cmin_%7B0%3Cs%3Cm%7D%5C!%5Cleft(%20Q_s(a%5E*)%20%2B%20C_%7Bm-1%2C%5C%2CT_%7Ba%5E*%7D(s)%7D%5Cright)%20%5Cleq%20%5Cmax_%7Bl%5Cleq%20s_i%20%5Cleq%20m%7D%5C!%5Cleft(%20Q_%7Bs_i%7D(i)%20%2B%0A%20%20%20%20C_%7Bm-1%2C%5C%2CT_i(s_i)%7D%5Cright)%20%5Cright%5C%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20%26%5Cleq%20l%20%2B%20%5Csum_%7Bm%3D1%7D%5E%7B%5Cinfty%7D%5Csum_%7Bs%3D1%7D%5E%7Bm-1%7D%5Csum_%7Bs_i%3Dl%7D%5E%7Bm-1%7D%20%5Cleft%5C%7B%20Q_s(a%5E*)%20%2B%20C_%7Bm%2C%5C%2CT_%7Ba%5E*%7D(s)%7D%20%5Cleq%20Q_%7Bs_i%7D(i)%20%2B%20C_%7Bm%2C%5C%2CT_i(s_i)%7D%20%5Cright%5C%7D%0A%20%20%20%20%5Cend%7Baligned%7D%0A%20%20%20%20%24%24%0A%0A%0A%20%20%20%20Now%2C%20%24Q_s(a%5E*)%20%2B%20C_%7Bm%2C%5C%2CT_%7Ba%5E*%7D(s)%7D%20%5Cleq%20Q_%7Bs_i%7D(i)%20%2B%20C_%7Bm%2C%5C%2CT_i(s_i)%7D%24%20implies%20that%20at%20least%0A%20%20%20%20one%20of%20the%20following%20must%20hold%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20Q_s(a%5E*)%20%26%5Cleq%20q_*(a%5E*)%20-%20C_%7Bm%2C%5C%2CT_%7Ba%5E*%7D(s)%7D%0A%20%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B((1)%20grossly%20underestimate%20%7D%20q_*(a%5E*)%5Ctext%7B)%7D%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20Q_%7Bs_i%7D(i)%20%26%5Cgeq%20q_*(i)%20%2B%20C_%7Bm%2C%5C%2CT_i(s_i)%7D%0A%20%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B((2)%20grossly%20overestimate%20%7D%20q_*(i)%5Ctext%7B)%7D%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20q_*(a%5E*)%20%26%5Cleq%20q_*(i)%20%2B%202%5C%2CC_%7Bm%2C%5C%2CT_i(s_i)%7D%0A%20%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B((3)%20arms%20too%20close%20together)%7D%7D%0A%20%20%20%20%5Cend%7Baligned%7D%0A%20%20%20%20%24%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20We%20now%20bound%20the%20probability%20of%20these%20events%20using%20the%20Chernoff%E2%80%93Hoeffding%20bound.%0A%20%20%20%20With%20%24C_%7Bm%2Cs%7D%20%3D%20%5Csqrt%7B2%5Cln%20m%20%2F%20s%7D%24%2C%20taking%20%24%5Cepsilon%20%3D%20C_%7Bm%2Cs%7D%24%20gives%0A%20%20%20%20%24e%5E%7B-2%5Cepsilon%5E2%20s%7D%20%3D%20e%5E%7B-4%5Cln%20m%7D%20%3D%20m%5E%7B-4%7D%24%2C%20so%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20%5CPr%5C!%5Cleft(Q_s(a%5E*)%20%5Cleq%20q_*(a%5E*)%20-%20C_%7Bm%2C%5C%2CT_%7Ba%5E*%7D(s)%7D%5Cright)%20%26%5Cleq%20m%5E%7B-4%7D%0A%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B(condition%201)%7D%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20%5CPr%5C!%5Cleft(Q_%7Bs_i%7D(i)%20%5Cgeq%20q_*(i)%20%2B%20C_%7Bm%2C%5C%2CT_i(s_i)%7D%5Cright)%20%26%5Cleq%20m%5E%7B-4%7D%0A%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B(condition%202)%7D%7D%0A%20%20%20%20%5Cend%7Baligned%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20For%20condition%20(3)%2C%20the%20choice%20%24l%20%3D%20%5Cleft%5Clceil%20%5Cdfrac%7B8%5Cln%20n%7D%7B%5CDelta_i%5E2%7D%20%5Cright%5Crceil%24%20forces%20it%20to%20be%20false%3A%20for%20every%20%24s_i%20%5Cgeq%20l%24%2C%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20%20%20%20%20q_*(a%5E*)%20-%20q_*(i)%20-%202%5C%2CC_%7Bm%2C%5C%2CT_i(s_i)%7D%0A%20%20%20%20%20%20%20%20%26%3D%20%5CDelta_i%20-%202%5Csqrt%7B%5Ctfrac%7B2%5Cln%20m%7D%7Bs_i%7D%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20%20%20%20%20%26%5Cgeq%20%5CDelta_i%20-%20%5CDelta_i%20%3D%200%0A%20%20%20%20%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B(so%20%7D%20q_*(a%5E*)%20%5Cgeq%20q_*(i)%20%2B%202C%20%5Ctext%7B%2C%20i.e.%20(3)%20cannot%20hold)%7D%7D%0A%20%20%20%20%5Cend%7Baligned%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Putting%20the%20pieces%20together%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20%20%20%20%20%5Cmathbb%7BE%7D%5BT_i(n)%5D%20%26%5Cleq%20%5Cleft%5Clceil%20%5Cfrac%7B8%5Cln%20n%7D%7B%5CDelta_i%5E2%7D%20%5Cright%5Crceil%20%2B%20%5Csum_%7Bm%3D1%7D%5E%7B%5Cinfty%7D%5Csum_%7Bs%3D1%7D%5E%7Bm-1%7D%5Csum_%7Bs_i%3Dl%7D%5E%7Bm-1%7D%20%5CBigl(%20%5CPr%5C!%5Cbigl(%5Ctext%7Bcond.%201%7D%5Cbigr)%20%2B%20%5CPr%5C!%5Cbigl(%5Ctext%7Bcond.%202%7D%5Cbigr)%20%5CBigr)%20%5C%5C%5B6pt%5D%20%26%5Cleq%20%5Cleft%5Clceil%20%5Cfrac%7B8%5Cln%20n%7D%7B%5CDelta_i%5E2%7D%20%5Cright%5Crceil%20%2B%20%5Csum_%7Bm%3D1%7D%5E%7B%5Cinfty%7D%5Csum_%7Bs%3D1%7D%5E%7Bm%7D%5Csum_%7Bs_i%3D1%7D%5E%7Bm%7D%202%5C%2Cm%5E%7B-4%7D%20%5C%5C%5B6pt%5D%20%26%5Cleq%20%5Cfrac%7B8%5Cln%20n%7D%7B%5CDelta_i%5E2%7D%20%2B%201%20%2B%20%5Cfrac%7B%5Cpi%5E2%7D%7B3%7D%0A%20%20%20%20%5Cend%7Baligned%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20where%20the%20last%20step%20uses%0A%20%20%20%20%24%5Cdisplaystyle%5Csum_%7Bm%3D1%7D%5E%7B%5Cinfty%7D%202m%5E2%20%5Ccdot%20m%5E%7B-4%7D%20%3D%202%5Csum_%7Bm%3D1%7D%5E%7B%5Cinfty%7D%20m%5E%7B-2%7D%20%3D%20%5Cfrac%7B%5Cpi%5E2%7D%7B3%7D%24.%0A%0A%20%20%20%20This%20concludes%20the%20proof.%20This%20bounds%20a%20**single**%20suboptimal%20arm%20%24i%24%3B%20summing%0A%20%20%20%20%24%5Cmathbb%7BE%7D%5BT_i(n)%5D%5C%2C%5CDelta_i%24%20over%20all%20arms%20gives%20the%20total%20regret%20of%20Theorem%201.%0A%0A%20%20%20%20%2F%2F%2F%20note%20%7C%20Lower%20bound%0A%20%20%20%20No%20bandit%20algorithm%20can%20do%20asymptotically%20better%20than%0A%20%20%20%20%24O%5C!%5Cleft(%5Cdfrac%7B%5Cln%20n%7D%7B%5CDelta_i%5E2%7D%5Cright)%24%20regret%20%E2%80%94%20this%20rate%20is%20optimal.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20---%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20np%2C%20torch)%3A%0A%20%20%20%20def%20UCB1(b%3A%20Bandit%2C%20c%3A%20float%2C%20n%3A%20int%20%3D%201000)%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20Q%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20UCB%20%3D%20torch.zeros(b.k)%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20play%20each%20arm%20once%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20t%20%3C%20b.k%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20t%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20play%20each%20arm%20that%20max.%20Q(i)%20%2B%20c(i)%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20UCB%20%3D%20Q%20%2B%20torch.sqrt(c*np.log(t)%2FN)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.argmax(UCB%2C%20dim%3D0).item()%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20N%5BA_t%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%5BA_t%5D%20%2B%3D%20(R_t%20-%20Q%5BA_t%5D)%2FN%5BA_t%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(UCB1%2C)%0A%0A%0A%40app.cell%0Adef%20_(UCB1%2C%20k%2C%20run_bandit_experiment%2C%20simple_algorithm)%3A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20%20%20%20%20algo_name%3D%22UCB1%20vs%20%CE%B5-greedy%22%2C%0A%20%20%20%20%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20%20%20%20%20configs%3D%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22label%22%3A%20%22UCB1%20(c%3D2)%22%2C%20%20%20%22algo_fn%22%3A%20UCB1%2C%20%20%20%20%20%20%20%20%20%20%20%20%20%22c%22%3A%202.0%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22label%22%3A%20%22%CE%B5-greedy%200.1%22%2C%20%22algo_fn%22%3A%20simple_algorithm%2C%20%22eps%22%3A%200.1%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22label%22%3A%20%22%CE%B5-greedy%200.01%22%2C%22algo_fn%22%3A%20simple_algorithm%2C%20%22eps%22%3A%200.01%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20%20PAC%20Bounds%20for%20the%20Multi-Armed%20Bandit%20Problem%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20We%20will%20use%20two%20standard%20tools%20repeatedly%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20%5Ctextbf%7BMarkov's%20inequality%3A%7D%20%5Cquad%20%26%5CPr(X%20%5Cgeq%20a)%20%5Cleq%20%5Cfrac%7B%5Cmathbb%7BE%7D%5BX%5D%7D%7Ba%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20%5Ctextbf%7BUnion%20bound%3A%7D%20%5Cquad%20%26%5CPr%5C!%5CBig(%5Ctextstyle%5Cbigcup_i%20A_i%5CBig)%20%5Cleq%20%5Csum_i%20%5CPr(A_i)%0A%20%20%20%20%5Cend%7Baligned%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%2F%2F%2F%20note%20%7C%20Naive%20%24(%5Cepsilon%2C%20%5Cdelta)%24%20algorithm%0A%20%20%20%20**Input%3A**%20%24%5Cepsilon%20%3E%200%2C%5C%20%5Cdelta%20%3E%200%24%20%26nbsp%3B%C2%B7%26nbsp%3B%20**Output%3A**%20an%20arm%0A%0A%20%20%20%20-%20For%20each%20arm%20%24a%20%5Cin%20A%24%2C%20sample%20it%20%24%5Cell%24%20times%2C%20where%20%24%5Cell%20%3D%20%5Cdfrac%7B2%7D%7B%5Cepsilon%5E2%7D%5Cln%5Cdfrac%7B2k%7D%7B%5Cdelta%7D%24%0A%20%20%20%20-%20Let%20%24Q(a)%24%20be%20the%20average%20reward%20of%20arm%20%24a%24%0A%20%20%20%20-%20**Return**%20%24a'%20%3D%20%5Cdisplaystyle%5Cargmax_%7Ba%5Cin%20A%7D%20Q(a)%24%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20Theorem%0A%20%20%20%20Naive%20%24(%5Cepsilon%2C%20%5Cdelta)%24%20is%20an%20%24(%5Cepsilon%2C%20%5Cdelta)%24-PAC%20algorithm%20with%20arm%20sample%20complexity%20%24O((k%2F%5Cepsilon%5E2)%5Clog%20(k%2F%5Cdelta))%24%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23%20Proof%0A%0A%20%20%20%20Let%20%24a'%24%20be%20a%20*bad*%20arm%2C%20i.e.%20%24q_*(a')%20%3C%20q_*(a%5E*)%20-%20%5Cepsilon%24.%20We%20bound%20the%0A%20%20%20%20probability%20that%20its%20empirical%20mean%20beats%20that%20of%20the%20optimal%20arm%20%24a%5E*%24.%20If%0A%20%20%20%20%24Q(a')%20%3E%20Q(a%5E*)%24%2C%20then%20at%20least%20one%20of%20the%20two%20estimates%20must%20be%20off%20by%0A%20%20%20%20%24%5Cepsilon%2F2%24%2C%20so%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cbegin%7Baligned%7D%0A%20%20%20%20%5CPr%5C!%5Cbig(Q(a')%20%3E%20Q(a%5E*)%5Cbig)%0A%20%20%20%20%26%5Cleq%20%5CPr%5C!%5CBig(Q(a')%20%3E%20q_*(a')%20%2B%20%5Ctfrac%7B%5Cepsilon%7D%7B2%7D%5C%20%5Ctext%7B%20or%20%7D%5C%20Q(a%5E*)%20%3C%20q_*(a%5E*)%20-%20%5Ctfrac%7B%5Cepsilon%7D%7B2%7D%5CBig)%20%5C%5C%5B4pt%5D%0A%20%20%20%20%26%5Cleq%20%5CPr%5C!%5CBig(Q(a')%20%3E%20q_*(a')%20%2B%20%5Ctfrac%7B%5Cepsilon%7D%7B2%7D%5CBig)%20%2B%20%5CPr%5C!%5CBig(Q(a%5E*)%20%3C%20q_*(a%5E*)%20-%20%5Ctfrac%7B%5Cepsilon%7D%7B2%7D%5CBig)%0A%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B(union%20bound)%7D%7D%20%5C%5C%5B4pt%5D%0A%20%20%20%20%26%5Cleq%202%5C%2Ce%5E%7B-2(%5Cepsilon%2F2)%5E2%20%5Cell%7D%20%3D%202%5C%2Ce%5E%7B-%5Cepsilon%5E2%20%5Cell%20%2F%202%7D%0A%20%20%20%20%26%26%20%7B%5Csmall%20%5Ctext%7B(Chernoff%E2%80%93Hoeffding)%7D%7D%0A%20%20%20%20%5Cend%7Baligned%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Choosing%20%24%5Cell%20%3D%20%5Cdfrac%7B2%7D%7B%5Cepsilon%5E2%7D%5Cln%5Cdfrac%7B2k%7D%7B%5Cdelta%7D%24%20makes%20this%20at%20most%0A%20%20%20%20%24%5Cdelta%2Fk%24.%20Summing%20over%20the%20at%20most%20%24k-1%24%20bad%20arms%20with%20the%20union%20bound%2C%20the%0A%20%20%20%20total%20failure%20probability%20is%20at%20most%20%24(k-1)%5Cdfrac%7B%5Cdelta%7D%7Bk%7D%20%5Cleq%20%5Cdelta%24%2C%20so%20the%0A%20%20%20%20returned%20arm%20is%20%24%5Cepsilon%24-optimal%20with%20probability%20%24%5Cgeq%201-%5Cdelta%24.%20%24%5Cblacksquare%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20The%20naive%20method%20pays%20a%20%24%5Clog%20k%24%20factor%20because%20the%20union%20bound%20spreads%20the%0A%20%20%20%20failure%20budget%20%24%5Cdelta%24%20across%20all%20%24k%24%20arms.%20**Median%20Elimination**%20avoids%20this%0A%20%20%20%20by%20proceeding%20in%20*phases*%3A%20each%20phase%20samples%20the%20surviving%20arms%20a%20moderate%0A%20%20%20%20number%20of%20times%2C%20discards%20the%20worse%20half%2C%20and%20tightens%20the%20accuracy%0A%20%20%20%20%24%5Cepsilon_%5Cell%24%20and%20confidence%20%24%5Cdelta_%5Cell%24%20as%20the%20set%20shrinks.%0A%0A%20%20%20%20%2F%2F%2F%20note%20%7C%20Median%20Elimination%20%24(%5Cepsilon%2C%20%5Cdelta)%24%20algorithm%0A%20%20%20%20**Input%3A**%20%24%5Cepsilon%20%3E%200%2C%5C%20%5Cdelta%20%3E%200%24%20%26nbsp%3B%C2%B7%26nbsp%3B%20**Output%3A**%20an%20arm%0A%0A%20%20%20%20Set%20%24S_1%20%3D%20A%2C%5C%20%5Cepsilon_1%20%3D%20%5Cepsilon%2F4%2C%5C%20%5Cdelta_1%20%3D%20%5Cdelta%2F2%2C%5C%20%5Cell%20%3D%201%24%2C%20then%20repeat%3A%0A%0A%20%20%20%20-%20Sample%20every%20arm%20%24a%20%5Cin%20S_%5Cell%24%20exactly%20%24%5Cdfrac%7B1%7D%7B(%5Cepsilon_%5Cell%2F2)%5E2%7D%5Cln%5Cdfrac%7B3%7D%7B%5Cdelta_%5Cell%7D%24%20times%3B%20let%20%24Q_%5Cell(a)%24%20be%20its%20average%20reward%0A%20%20%20%20-%20Let%20%24m_%5Cell%24%20be%20the%20median%20of%20%24%5C%7BQ_%5Cell(a)%20%3A%20a%20%5Cin%20S_%5Cell%5C%7D%24%0A%20%20%20%20-%20%24S_%7B%5Cell%2B1%7D%20%3D%20S_%5Cell%20%5Csetminus%20%5C%7Ba%20%3A%20Q_%5Cell(a)%20%3C%20m_%5Cell%5C%7D%24%20%26nbsp%3B*(drop%20the%20worse%20half)*%0A%20%20%20%20-%20%24%5Cepsilon_%7B%5Cell%2B1%7D%20%3D%20%5Ctfrac%7B3%7D%7B4%7D%5Cepsilon_%5Cell%2C%5Cquad%20%5Cdelta_%7B%5Cell%2B1%7D%20%3D%20%5Cdelta_%5Cell%2F2%2C%5Cquad%20%5Cell%20%5Cleftarrow%20%5Cell%20%2B%201%24%0A%0A%20%20%20%20**Until**%20%24%7CS_%5Cell%7C%20%3D%201%24.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20Theorem%0A%20%20%20%20Median%20Elimination%20Algorithm%20is%20an%20%24(%5Cepsilon%2C%20%5Cdelta)%24-PAC%20algorithm%20with%20arm%20sample%20complexity%20%24O((k%2F%5Cepsilon%5E2)%5Clog%20(1%2F%5Cdelta))%24%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%23%20Proof%0A%0A%20%20%20%20The%20heart%20of%20the%20analysis%20is%20a%20per-phase%20guarantee.%0A%0A%20%20%20%20%2F%2F%2F%20admonition%20%7C%20Lemma%201%0A%20%20%20%20For%20every%20phase%20%24%5Cell%24%2C%0A%20%20%20%20%24%24%0A%20%20%20%20%5CPr%5C!%5CBig%5B%5Cmax_%7Bj%5Cin%20S_%5Cell%7D%20q_*(j)%20%5C%3B%5Cleq%5C%3B%20%5Cmax_%7Bi%5Cin%20S_%7B%5Cell%2B1%7D%7D%20q_*(i)%20%2B%20%5Cepsilon_%5Cell%5CBig%5D%20%5C%3B%5Cgeq%5C%3B%201-%5Cdelta_%5Cell%20.%0A%20%20%20%20%24%24%0A%20%20%20%20%2F%2F%2F%0A%0A%20%20%20%20In%20words%3A%20the%20best%20arm%20we%20*keep*%20is%20no%20worse%20than%20the%20best%20arm%20we%20*had*%2C%20up%20to%0A%20%20%20%20a%20slack%20of%20%24%5Cepsilon_%5Cell%24%20%E2%80%94%20and%20this%20holds%20with%20probability%20%24%5Cgeq%201-%5Cdelta_%5Cell%24.%0A%0A%20%20%20%20**Proof%20of%20Lemma%201.**%20Take%20phase%20%24%5Cell%24%20(set%20%24%5Cell%20%3D%201%24%20without%20loss%20of%0A%20%20%20%20generality)%20and%20let%20%24a_%5Cell%5E*%24%20be%20the%20best%20arm%20in%20%24S_%5Cell%24.%20First%20bound%20the%0A%20%20%20%20chance%20that%20we%20badly%20*underestimate*%20it%3A%0A%20%20%20%20%24%24%0A%20%20%20%20E%20%3D%20%5CBig%5C%7B%5C%2C%20Q_%5Cell(a_%5Cell%5E*)%20%3C%20q_*(a_%5Cell%5E*)%20-%20%5Ctfrac%7B%5Cepsilon_%5Cell%7D%7B2%7D%20%5C%2C%5CBig%5C%7D%2C%0A%20%20%20%20%5Cqquad%20%5CPr%5BE%5D%20%5Cleq%20%5Ctfrac%7B%5Cdelta_%5Cell%7D%7B3%7D%2C%0A%20%20%20%20%24%24%0A%20%20%20%20by%20Chernoff%E2%80%93Hoeffding%20with%20the%20chosen%20sample%20count.%20Now%20condition%20on%0A%20%20%20%20%24%5Coverline%7BE%7D%24%20and%20call%20an%20arm%20%24j%24%20**bad**%20if%20it%20is%20*not*%20%24%5Cepsilon_%5Cell%24-optimal%0A%20%20%20%20yet%20still%20beats%20the%20best%20arm's%20estimate.%20For%20any%20such%20%24j%24%2C%0A%20%20%20%20%24%24%0A%20%20%20%20%5CPr%5C!%5CBig%5B%5C%2C%20Q_%5Cell(j)%20%5Cgeq%20Q_%5Cell(a_%5Cell%5E*)%20%5C%3B%5CBig%7C%5C%3B%20Q_%5Cell(a_%5Cell%5E*)%20%5Cgeq%20q_*(a_%5Cell%5E*)%20-%20%5Ctfrac%7B%5Cepsilon_%5Cell%7D%7B2%7D%20%5C%2C%5CBig%5D%20%5Cleq%20%5Ctfrac%7B%5Cdelta_%5Cell%7D%7B3%7D.%20%5Ctag%7B1%7D%0A%20%20%20%20%24%24%0A%20%20%20%20Letting%20%24%5C%23%5Ctext%7Bbad%7D%24%20count%20such%20arms%2C%20%24(1)%24%20gives%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbb%7BE%7D%5Cbig%5B%5C%2C%5C%23%5Ctext%7Bbad%7D%20%5C%3B%5Cbig%7C%5C%3B%20%5Coverline%7BE%7D%5C%2C%5Cbig%5D%20%3C%20%7CS_%5Cell%7C%5C%2C%5Ctfrac%7B%5Cdelta_%5Cell%7D%7B3%7D.%0A%20%20%20%20%24%24%0A%20%20%20%20A%20phase%20*fails*%20(drops%20the%20true%20best%20arm)%20only%20if%20at%20least%20half%20the%20survivors%0A%20%20%20%20are%20bad.%20By%20**Markov's%20inequality**%2C%0A%20%20%20%20%24%24%0A%20%20%20%20%5CPr%5C!%5CBig%5B%5C%2C%5C%23%5Ctext%7Bbad%7D%20%5Cgeq%20%5Ctfrac%7B%7CS_%5Cell%7C%7D%7B2%7D%20%5C%3B%5CBig%7C%5C%3B%20%5Coverline%7BE%7D%5C%2C%5CBig%5D%0A%20%20%20%20%5Cleq%20%5Cfrac%7B%7CS_%5Cell%7C%5C%2C%5Cdelta_%5Cell%2F3%7D%7B%7CS_%5Cell%7C%2F2%7D%20%3D%20%5Ctfrac%7B2%5Cdelta_%5Cell%7D%7B3%7D.%0A%20%20%20%20%24%24%0A%20%20%20%20Combining%20the%20two%20failure%20modes%20(%24E%24%2C%20and%20too-many-bad)%20with%20the%20**union%0A%20%20%20%20bound**%2C%20a%20phase%20fails%20with%20probability%20at%20most%0A%20%20%20%20%24%5Ctfrac%7B%5Cdelta_%5Cell%7D%7B3%7D%20%2B%20%5Ctfrac%7B2%5Cdelta_%5Cell%7D%7B3%7D%20%3D%20%5Cdelta_%5Cell%24.%20%24%5Cblacksquare%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20**From%20the%20lemma%20to%20the%20theorem.**%20Two%20telescoping%20sums%20finish%20the%20argument.%0A%0A%20%20%20%20*Accuracy.*%20Summing%20the%20per-phase%20slack%20over%20the%20%24%5Clceil%5Clog_2%20k%5Crceil%24%20phases%2C%0A%20%20%20%20%24%24%0A%20%20%20%20%5Csum_%7B%5Cell%20%5Cgeq%201%7D%20%5Cepsilon_%5Cell%20%3D%20%5Cfrac%7B%5Cepsilon%7D%7B4%7D%5Csum_%7B%5Cell%20%5Cgeq%200%7D%5CBig(%5Ctfrac%7B3%7D%7B4%7D%5CBig)%5E%7B%5Cell%7D%20%3D%20%5Cfrac%7B%5Cepsilon%7D%7B4%7D%5Ccdot%204%20%3D%20%5Cepsilon%2C%0A%20%20%20%20%24%24%0A%20%20%20%20so%20the%20surviving%20arm%20is%20%24%5Cepsilon%24-optimal.%0A%0A%20%20%20%20*Confidence.*%20Summing%20the%20per-phase%20failure%20probabilities%2C%0A%20%20%20%20%24%24%0A%20%20%20%20%5Csum_%7B%5Cell%20%5Cgeq%201%7D%20%5Cdelta_%5Cell%20%3D%20%5Cfrac%7B%5Cdelta%7D%7B2%7D%5Csum_%7B%5Cell%20%5Cgeq%200%7D%5CBig(%5Ctfrac%7B1%7D%7B2%7D%5CBig)%5E%7B%5Cell%7D%20%3D%20%5Cdelta%2C%0A%20%20%20%20%24%24%0A%20%20%20%20so%20the%20algorithm%20succeeds%20with%20probability%20%24%5Cgeq%201-%5Cdelta%24.%0A%0A%20%20%20%20*Sample%20complexity.*%20Phase%20%24%5Cell%24%20has%20%24%7CS_%5Cell%7C%20%5Cleq%20k%2F2%5E%7B%5C%2C%5Cell-1%7D%24%20arms%2C%20each%0A%20%20%20%20pulled%20%24%5Ctfrac%7B1%7D%7B(%5Cepsilon_%5Cell%2F2)%5E2%7D%5Cln%5Ctfrac%7B3%7D%7B%5Cdelta_%5Cell%7D%24%20times.%20Summing%0A%20%20%20%20this%20geometric%20series%20over%20phases%20gives%20a%20total%20of%0A%20%20%20%20%24%24%0A%20%20%20%20O%5C!%5Cleft(%5Cfrac%7Bk%7D%7B%5Cepsilon%5E2%7D%5Clog%5Cfrac%7B1%7D%7B%5Cdelta%7D%5Cright)%2C%0A%20%20%20%20%24%24%0A%20%20%20%20which%20replaces%20the%20naive%20method's%20%24%5Clog(k%2F%5Cdelta)%24%20with%20%24%5Clog(1%2F%5Cdelta)%24%20%E2%80%94%0A%20%20%20%20removing%20the%20%24%5Clog%20k%24%20factor.%20%24%5Cblacksquare%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20np%2C%20torch)%3A%0A%20%20%20%20def%20naive_pac(b%3A%20Bandit%2C%20eps%3A%20float%20%3D%200.5%2C%20delta%3A%20float%20%3D%200.1)%3A%0A%20%20%20%20%20%20%20%20%23%20samples%20per%20arm%3A%20l%20%3D%20(2%20%2F%20e%5E2)%20%C2%B7%20ln(2k%20%2F%20d)%0A%20%20%20%20%20%20%20%20l%20%3D%20int(np.ceil((2.0%20%2F%20eps**2)%20*%20np.log(2.0%20*%20b.k%20%2F%20delta)))%0A%0A%20%20%20%20%20%20%20%20%23%20arm%20a%20sampled%20l%20times%20~%20q*(a)%20%2B%20N(0%2C1)%3B%20take%20the%20mean%20over%20the%20l%20draws%0A%20%20%20%20%20%20%20%20Q%20%3D%20b.qs%20%2B%20torch.randn(b.k%2C%20l).mean(dim%3D1)%0A%0A%20%20%20%20%20%20%20%20a_hat%20%3D%20torch.argmax(Q).item()%0A%20%20%20%20%20%20%20%20n_samples%20%3D%20b.k%20*%20l%0A%20%20%20%20%20%20%20%20return%20a_hat%2C%20n_samples%0A%0A%20%20%20%20return%20(naive_pac%2C)%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20np%2C%20torch)%3A%0A%20%20%20%20def%20median_elimination(b%3A%20Bandit%2C%20eps%3A%20float%20%3D%200.5%2C%20delta%3A%20float%20%3D%200.1)%3A%0A%20%20%20%20%20%20%20%20S%20%3D%20list(range(b.k))%0A%20%20%20%20%20%20%20%20eps_l%2C%20delta_l%20%3D%20eps%20%2F%204.0%2C%20delta%20%2F%202.0%0A%20%20%20%20%20%20%20%20n_samples%20%3D%200%0A%0A%20%20%20%20%20%20%20%20while%20len(S)%20%3E%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20samples%20per%20surviving%20arm%20this%20round%3A%20(1%20%2F%20(e_l%2F2)%5E2)%20%C2%B7%20ln(3%20%2F%20d_l)%0A%20%20%20%20%20%20%20%20%20%20%20%20t_l%20%3D%20int(np.ceil((1.0%20%2F%20(eps_l%20%2F%202.0)%20**%202)%20*%20np.log(3.0%20%2F%20delta_l)))%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20idx%20%3D%20torch.tensor(S)%0A%20%20%20%20%20%20%20%20%20%20%20%20Q%20%3D%20b.qs%5Bidx%5D%20%2B%20torch.randn(len(S)%2C%20t_l).mean(dim%3D1)%20%20%20%23%20~%20q*(a)%20%2B%20N(0%2C1)%0A%20%20%20%20%20%20%20%20%20%20%20%20n_samples%20%2B%3D%20t_l%20*%20len(S)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20keep%20the%20better%20half%3A%20top%20%E2%8C%88%7CS%7C%2F2%E2%8C%89%20arms%20by%20empirical%20mean%0A%20%20%20%20%20%20%20%20%20%20%20%20keep%20%3D%20(len(S)%20%2B%201)%20%2F%2F%202%0A%20%20%20%20%20%20%20%20%20%20%20%20order%20%3D%20torch.argsort(Q%2C%20descending%3DTrue)%0A%20%20%20%20%20%20%20%20%20%20%20%20S%20%3D%20%5BS%5Border%5Bi%5D.item()%5D%20for%20i%20in%20range(keep)%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20eps_l%20*%3D%200.75%0A%20%20%20%20%20%20%20%20%20%20%20%20delta_l%20%2F%3D%202.0%0A%0A%20%20%20%20%20%20%20%20return%20S%5B0%5D%2C%20n_samples%0A%0A%20%20%20%20return%20(median_elimination%2C)%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20mo%2C%20pd%2C%20px%2C%20torch)%3A%0A%20%20%20%20def%20run_pac_experiment(algos%2C%20eps_values%3D(0.3%2C%200.5%2C%200.7%2C%201.0)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20delta%3D0.1%2C%20n_runs%3D200%2C%20k%3D10)%3A%0A%20%20%20%20%20%20%20%20%22%22%22PAC%20analogue%20of%20run_bandit_experiment.%0A%0A%20%20%20%20%20%20%20%20algos%3A%20dict%20%7Blabel%20-%3E%20callable(bandit%2C%20eps%3D%2C%20delta%3D)%20-%3E%20(arm%2C%20n_samples)%7D%0A%20%20%20%20%20%20%20%20Sweeps%20%CE%B5%3B%20for%20each%20(algorithm%2C%20%CE%B5)%20measures%2C%20over%20n_runs%20random%20k-armed%0A%20%20%20%20%20%20%20%20bandits%2C%20the%20empirical%20%CE%B5-correct%20rate%20and%20the%20average%20pulls%20used.%0A%20%20%20%20%20%20%20%20Returns%20two%20stacked%20figures%3A%20sample%20complexity%20and%20%CE%B5-correctness%20vs%20%CE%B5.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20def%20eval_once(algo_fn%2C%20eps)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20successes%2C%20samples%20%3D%200%2C%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_%20in%20range(n_runs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bandit%20%3D%20Bandit(k)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20a_star%20%3D%20torch.argmax(bandit.qs).item()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20threshold%20%3D%20bandit.qs%5Ba_star%5D.item()%20-%20eps%20%20%20%20%20%23%20%CE%B5-optimal%20cutoff%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20a_hat%2C%20n%20%3D%20algo_fn(bandit%2C%20eps%3Deps%2C%20delta%3Ddelta)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20bandit.qs%5Ba_hat%5D.item()%20%3E%3D%20threshold%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20successes%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20samples.append(n)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20successes%20%2F%20n_runs%2C%20sum(samples)%20%2F%20len(samples)%0A%0A%20%20%20%20%20%20%20%20rows%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20label%2C%20fn%20in%20algos.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20eps%20in%20eps_values%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20succ%2C%20avg%20%3D%20eval_once(fn%2C%20eps)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rows.append(%7B%22%CE%B5%22%3A%20eps%2C%20%22Algorithm%22%3A%20label%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%CE%B5-correct%20rate%22%3A%20succ%2C%20%22Avg.%20samples%22%3A%20avg%7D)%0A%20%20%20%20%20%20%20%20df%20%3D%20pd.DataFrame(rows)%0A%0A%20%20%20%20%20%20%20%20fig_samples%20%3D%20px.line(%0A%20%20%20%20%20%20%20%20%20%20%20%20df%2C%20x%3D%22%CE%B5%22%2C%20y%3D%22Avg.%20samples%22%2C%20color%3D%22Algorithm%22%2C%20markers%3DTrue%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20log_y%3DTrue%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20title%3Df%22Sample%20complexity%20vs%20%CE%B5%20(%CE%B4%3D%7Bdelta%7D%2C%20%7Bn_runs%7D%20runs%2C%20k%3D%7Bk%7D)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20fig_success%20%3D%20px.line(%0A%20%20%20%20%20%20%20%20%20%20%20%20df%2C%20x%3D%22%CE%B5%22%2C%20y%3D%22%CE%B5-correct%20rate%22%2C%20color%3D%22Algorithm%22%2C%20markers%3DTrue%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20title%3Df%22Empirical%20%CE%B5-correctness%20vs%20%CE%B5%20(%CE%B4%3D%7Bdelta%7D%2C%20%7Bn_runs%7D%20runs%2C%20k%3D%7Bk%7D)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20fig_success.update_yaxes(range%3D%5B0%2C%201.05%5D%2C%20tickformat%3D%22.0%25%22)%0A%20%20%20%20%20%20%20%20fig_success.add_hline(%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D1%20-%20delta%2C%20line_dash%3D%22dash%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20annotation_text%3D%221%20%E2%88%92%20%CE%B4%20guarantee%22%2C%20annotation_position%3D%22bottom%20right%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20return%20mo.vstack(%5Bmo.ui.plotly(fig_samples)%2C%20mo.ui.plotly(fig_success)%5D)%0A%0A%20%20%20%20return%20(run_pac_experiment%2C)%0A%0A%0A%40app.cell%0Adef%20_(median_elimination%2C%20naive_pac%2C%20run_pac_experiment)%3A%0A%20%20%20%20run_pac_experiment(%0A%20%20%20%20%20%20%20%20algos%3D%7B%22Naive%22%3A%20naive_pac%2C%20%22Median%20Elimination%22%3A%20median_elimination%7D%2C%0A%20%20%20%20%20%20%20%20eps_values%3D(0.3%2C%200.5%2C%200.7%2C%201.0)%2C%0A%20%20%20%20%20%20%20%20delta%3D0.1%2C%0A%20%20%20%20%20%20%20%20n_runs%3D200%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%2F%2F%2F%20note%20%7C%20Reading%20the%20result%0A%20%20%20%20Both%20methods%20return%20an%20%CE%B5-optimal%20arm%20well%20above%20the%20%241-%5Cdelta%20%3D%2090%5C%25%24%20guarantee.%0A%20%20%20%20But%20notice%20**Median%20Elimination%20uses%20far%20*more*%20samples%20than%20Naive%20at%20%24k%3D10%24.**%0A%20%20%20%20This%20is%20expected%3A%20Median%20Elimination's%20advantage%20is%20*asymptotic%20in%20%24k%24*%20%E2%80%94%20it%0A%20%20%20%20replaces%20the%20%24%5Clog%20k%24%20factor%20of%20Naive%20with%20%24%5Clog(1%2F%5Cdelta)%24%20%E2%80%94%20yet%20its%0A%20%20%20%20per-round%20constants%20(the%20%244%2F%5Cvarepsilon_%5Cell%5E2%24%20sampling%20and%20the%20geometric%0A%20%20%20%20schedule%20over%20%24%5Clog_2%20k%24%20rounds)%20are%20large.%20The%20crossover%20where%20it%20wins%20only%0A%20%20%20%20appears%20for%20very%20large%20%24k%24.%20For%20a%20handful%20of%20arms%2C%20the%20simpler%20Naive%20method%20is%0A%20%20%20%20cheaper.%0A%0A%20%20%20%20Caveat%3A%20the%20sample-complexity%20bounds%20assume%20rewards%20in%20%24%5B0%2C1%5D%24%2C%20whereas%20this%0A%20%20%20%20testbed%20uses%20unbounded%20%24%5Cmathcal%7BN%7D(q_*(a)%2C%201)%24%20rewards%2C%20so%20the%20empirical%0A%20%20%20%20success%20rate%20won't%20match%20the%20theory%20exactly.%0A%20%20%20%20%2F%2F%2F%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%23%20**Thompson%20Sampling**%0A%0A%20%20%20%20Every%20method%20so%20far%20acts%20on%20a%20*point*%20estimate%20%24Q(a)%24%20%E2%80%94%20optionally%20inflated%20by%0A%20%20%20%20a%20confidence%20bonus%2C%20as%20in%20UCB1.%20**Thompson%20Sampling**%20takes%20a%20Bayesian%20view%0A%20%20%20%20instead%3A%20it%20keeps%20a%20*posterior%20distribution*%20over%20each%20arm's%20true%20value%0A%20%20%20%20%24q_*(a)%24%2C%20and%20at%20every%20step%20it%20**samples**%20one%20plausible%20value%20per%20arm%20from%0A%20%20%20%20those%20posteriors%20and%20plays%20the%20arm%20with%20the%20highest%20sample.%20Promising%20or%20still%0A%20%20%20%20uncertain%20arms%20draw%20a%20high%20sample%20often%20enough%20to%20be%20explored%3B%20confidently%20bad%0A%20%20%20%20arms%20rarely%20do.%20Exploration%20then%20emerges%20automatically%20from%20posterior%0A%20%20%20%20uncertainty%20%E2%80%94%20there%20is%20no%20%24%5Cvarepsilon%24%20or%20bonus%20to%20tune.%0A%0A%20%20%20%20Our%20testbed%20has%20Gaussian%20rewards%20%24R%20%5Csim%20%5Cmathcal%7BN%7D(q_*(a)%2C%201)%24%20with%20true%0A%20%20%20%20values%20drawn%20%24q_*(a)%20%5Csim%20%5Cmathcal%7BN%7D(0%2C1)%24%2C%20so%20we%20use%20exactly%20that%20as%20the%0A%20%20%20%20prior.%20With%20a%20%24%5Cmathcal%7BN%7D(0%2C1)%24%20prior%20and%20unit-variance%20Gaussian%20likelihood%2C%0A%20%20%20%20the%20posterior%20over%20an%20arm's%20mean%20after%20%24N_a%24%20pulls%20with%20reward-sum%20%24S_a%24%20is%0A%20%20%20%20conjugate%20and%20Gaussian%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20q_*(a)%20%5Cmid%20%5Ctext%7Bdata%7D%20%5C%3B%5Csim%5C%3B%20%5Cmathcal%7BN%7D%5C!%5Cleft(%5Cfrac%7BS_a%7D%7B1%20%2B%20N_a%7D%2C%5C%20%5Cfrac%7B1%7D%7B1%20%2B%20N_a%7D%5Cright).%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Each%20step%20we%20draw%20%24%5Ctheta_a%24%20from%20this%20posterior%20for%20every%20arm%20and%20select%0A%20%20%20%20%24A_t%20%3D%20%5Cargmax_a%20%5Ctheta_a%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Bandit%2C%20torch)%3A%0A%20%20%20%20def%20thompson_sampling(b%3A%20Bandit%2C%20n%3A%20int%20%3D%201000)%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20torch.zeros(b.k)%0A%20%20%20%20%20%20%20%20S%20%3D%20torch.zeros(b.k)%20%20%20%20%20%23%20running%20sum%20of%20rewards%20per%20arm%0A%0A%20%20%20%20%20%20%20%20%23%20for%20stat-tracking%0A%20%20%20%20%20%20%20%20R%20%3D%20torch.zeros(n)%20%20%20%20%20%20%20%23%20raw%20per-step%20reward%2C%20not%20cumulative%20avg%0A%20%20%20%20%20%20%20%20q_a%20%3D%20torch.argmax(b.qs%2C%20dim%3D0).item()%0A%20%20%20%20%20%20%20%20Qopt%20%3D%20torch.zeros(n)%0A%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20posterior%20over%20each%20arm's%20mean%3A%20N(0%2C1)%20prior%2C%20unit-variance%20likelihood%0A%20%20%20%20%20%20%20%20%20%20%20%20post_var%20%3D%201.0%20%2F%20(1.0%20%2B%20N)%0A%20%20%20%20%20%20%20%20%20%20%20%20post_mean%20%3D%20S%20*%20post_var%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20%3D%20S%20%2F%20(1%20%2B%20N)%0A%20%20%20%20%20%20%20%20%20%20%20%20theta%20%3D%20post_mean%20%2B%20torch.sqrt(post_var)%20*%20torch.randn(b.k)%0A%20%20%20%20%20%20%20%20%20%20%20%20A_t%20%3D%20torch.argmax(theta%2C%20dim%3D0).item()%20%20%20%20%20%20%23%20play%20the%20best%20sample%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20R_t%20%3D%20b.act(A_t)%0A%20%20%20%20%20%20%20%20%20%20%20%20N%5BA_t%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20S%5BA_t%5D%20%2B%3D%20R_t%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20stat%20tracking%0A%20%20%20%20%20%20%20%20%20%20%20%20R%5Bt%5D%20%3D%20R_t%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20raw%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20Qopt%5Bt%5D%20%3D%201.0%20if%20A_t%20%3D%3D%20q_a%20else%200.0%20%20%20%23%20binary%2C%20not%20cumulative%0A%0A%20%20%20%20%20%20%20%20Q%20%3D%20S%20%2F%20torch.clamp(N%2C%20min%3D1.0)%0A%20%20%20%20%20%20%20%20return%20Q%2C%20R%2C%20Qopt%0A%0A%20%20%20%20return%20(thompson_sampling%2C)%0A%0A%0A%40app.cell%0Adef%20_(UCB1%2C%20k%2C%20run_bandit_experiment%2C%20simple_algorithm%2C%20thompson_sampling)%3A%0A%20%20%20%20run_bandit_experiment(%0A%20%20%20%20%20%20%20%20algo_name%3D%22Thompson%20Sampling%20vs%20UCB1%20vs%20%CE%B5-greedy%22%2C%0A%20%20%20%20%20%20%20%20k%3Dk%2C%0A%20%20%20%20%20%20%20%20configs%3D%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%22label%22%3A%20%22Thompson%20Sampling%22%2C%20%22algo_fn%22%3A%20thompson_sampling%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%22label%22%3A%20%22UCB1%20(c%3D2)%22%2C%20%20%20%20%20%20%20%20%22algo_fn%22%3A%20UCB1%2C%20%20%20%20%20%20%20%20%20%20%20%20%20%22c%22%3A%202.0%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%22label%22%3A%20%22%CE%B5-greedy%200.1%22%2C%20%20%20%20%20%20%22algo_fn%22%3A%20simple_algorithm%2C%20%22eps%22%3A%200.1%7D%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A