import%20marimo%0A%0A__generated_with%20%3D%20%220.19.2%22%0Aapp%20%3D%20marimo.App(width%3D%22full%22%2C%20app_title%3D%22RL2%3A%20Multi-armed%20bandits%22)%0A%0Awith%20app.setup(hide_code%3DTrue)%3A%0A%20%20%20%20%23%20Initialization%20code%20that%20runs%20before%20all%20other%20cells%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20seaborn%20as%20sns%0A%20%20%20%20import%20itertools%0A%20%20%20%20import%20warnings%20%0A%20%20%20%20warnings.filterwarnings(%22ignore%22%2C%20category%3DRuntimeWarning)%0A%20%20%20%20warnings.filterwarnings(%22ignore%22%2C%20category%3DUserWarning)%0A%20%20%20%20np.random.seed(308)%0A%0A%20%20%20%20def%20running_avg(data%2C%20window_size)%3A%0A%20%20%20%20%20%20%20%20res%20%3D%20np.zeros(len(data)-window_size)%0A%20%20%20%20%20%20%20%20sum%20%3D%200%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(window_size)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20data%5Bi%5D%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(len(data)-window_size)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20res%5Bi%5D%20%3D%20sum%20%2F%20window_size%0A%20%20%20%20%20%20%20%20%20%20%20%20sum%20-%3D%20data%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20data%5Bi%20%2B%20window_size%5D%0A%20%20%20%20%20%20%20%20return%20res%0A%0A%20%20%20%20def%20configure_seaborn(**kwargs)%3A%0A%20%20%20%20%20%20%20%20sns.set_context(%22notebook%22)%0A%20%20%20%20%20%20%20%20sns.set_theme(sns.plotting_context(%22notebook%22%2C%20font_scale%3D1)%2C%20style%3D%22whitegrid%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rc%3D%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20grid%20activation%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22axes.grid%22%3A%20False%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20grid%20appearance%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22grid.color%22%3A%20%22%23BFBFBF%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22axes.edgecolor%22%3A%20%22%23BFBFBF%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22axes.linewidth%22%3A%200.8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22grid.linewidth%22%3A%200.5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22grid.alpha%22%3A%200.4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'font.family'%3A'sans-serif'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20'font.sans-serif'%3A%5B'Lato'%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C)%0A%0A%20%20%20%20%20%20%20%20palette%20%3D%20%5B%22%233D405B%22%2C%20%22%23E08042%22%2C%20%22%2354AB69%22%2C%20%22%23CE2F49%22%2C%20%22%23A26EBF%22%2C%20%22%2375523A%22%2C%20%22%23D12AA2%22%2C%20%22%23E0D06F%22%2C%20%22%236F9AA7%22%2C%20%22%233359C4%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%2376455B%22%5D%0A%0A%20%20%20%20%20%20%20%20sns.set_palette(palette)%0A%20%20%20%20configure_seaborn()%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23Reinforcement%20Learning%20Chapter%202%3A%20Multi-armed%20bandits%0A%0A%20%20%20%20Author%3A%20No%C3%A9%20Lallouet%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Introduction%0A%0A%20%20%20%20This%20notebook%20explores%20the%20multi-armed%20bandit%20problem%20and%20ways%20to%20solve%20it%20using%20different%20algorithms.%0A%0A%20%20%20%20The%20multi-armed%20bandit%20problem%20is%20a%20very%20nice%20introduction%20to%20more%20general%20RL%20problems.%20Some%20of%20the%20concepts%20that%20will%20be%20explored%20in%20this%20notebook%20include%3A%0A%20%20%20%20-%20Exploration%20%2F%20exploitation%20trade-off%0A%20%20%20%20-%20Action%20value%20estimates%0A%20%20%20%20-%20%24%5Cvarepsilon%24-greedy%20algorithm%0A%20%20%20%20-%20Optimistic%20initialization%0A%20%20%20%20-%20UCB%20action%20selection%0A%0A%20%20%20%20We%20will%20implement%20several%20algorithms%20to%20solve%20the%20multi-armed%20bandit%20problem%20and%20compare%20their%20performance.%0A%0A%20%20%20%20%23%23%23%20Problem%20statement%0A%0A%20%20%20%20The%20multi-armed%20bandit%20problem%20is%20defined%20as%20follows%3A%0A%0A%20%20%20%20The%20agent%20is%20faced%20with%20%24k%24%20arms.%20Pulling%20an%20arm%20returns%20a%20reward%20drawn%20from%20a%20probability%20distribution%20specific%20to%20that%20arm%2C%20but%20unknown%20to%20the%20agent.%20The%20agent%20chooses%20an%20action%20at%20each%20time%20step%2C%20and%20the%20goal%20is%20to%20maximize%20the%20total%20reward%20over%20time.%0A%0A%20%20%20%20The%20reward%20obtained%20by%20pulling%20arm%20%24k%24%20is%20drawn%20from%20a%20normal%20distribution%20%24%5Cmathcal%7BN%7D(%5Cmu_k%2C%20%5Csigma%5E2)%24%2C%20where%20%24%5Cmu_k%24%20is%20the%20true%20mean%20reward%20for%20arm%20%24k%24%20and%20%24%5Csigma%5E2%24%20is%20the%20variance.%20The%20variance%20is%20identical%20between%20all%20arms.%20The%20means%20%24%5Cmu_k%24%20are%20drawn%20from%20a%20normal%20distribution%20%24%5Cmathcal%7BN%7D(%5Cmu%2C%201)%24%20at%20the%20start%20of%20each%20run%2C%20where%20%24%5Cmu%24%20is%20a%20hyperparameter%20of%20the%20environment.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%23%20Defining%20the%20environment%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%20class%20Arm%3A%0A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20mu%2C%20sigma%3D1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.mu%20%3D%20mu%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sigma%20%3D%20sigma%0A%0A%20%20%20%20%20%20%20%20def%20pull(self%2C%20size%3D1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20np.random.normal(self.mu%2C%20self.sigma%2C%20size).squeeze()%0A%0A%20%20%20%20class%20MultiArmedBandit%3A%0A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20k%3D10%2C%20mu%3D0%2C%20sigma%3D1)%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.mu%20%3D%20mu%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sigma%20%3D%20sigma%0A%20%20%20%20%20%20%20%20%20%20%20%20self.arms%20%3D%20%5BArm(np.random.normal(mu%2C%201)%2C%20sigma)%20for%20_%20in%20range(k)%5D%0A%20%20%20%20return%20(MultiArmedBandit%2C)%0A%0A%0A%40app.cell%0Adef%20_(MultiArmedBandit)%3A%0A%20%20%20%20bandit%20%3D%20MultiArmedBandit(k%3D10%2C%20mu%3D0%2C%20sigma%3D1)%0A%20%20%20%20rewards%20%3D%20np.array(%5Barm.pull(size%3D10000)%20for%20arm%20in%20bandit.arms%5D)%0A%20%20%20%20return%20bandit%2C%20rewards%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(bandit%2C%20plot_problem)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20%7Bmo.as_html(plot_problem())%7D%0A%20%20%20%20From%20the%20above%20graph%20representing%20the%20distribution%20of%20rewards%20obtained%20by%20pulling%20each%20arm%2C%20we%20can%20clearly%20see%20that%20arm%20%7Bnp.argmax(%5Barm.mu%20for%20arm%20in%20bandit.arms%5D)%7D%20is%20the%20best%20choice.%20%0A%0A%20%20%20%20However%2C%20the%20agent%20doesn't%20know%20this%3A%20they%20must%20find%20the%20best%20arm%20through%20experience%20acquired%20by%20pulling%20the%20arms%20and%20observing%20the%20rewards.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20The%20%24%5Cvarepsilon%24-greedy%20algorithm%0A%0A%20%20%20%20The%20%24%5Cvarepsilon%24-greedy%20algorithm%20is%20a%20simple%20algorithm%20that%20allows%20the%20agent%20to%20balance%20exploration%20and%20exploitation.%0A%0A%20%20%20%20The%20algorithm%20works%20as%20follows%3A%0A%0A%20%20%20%201.%20Select%20an%20action%3A%0A%20%20%20%20%20%20%20%20-%20With%20probability%20%24%5Cvarepsilon%24%2C%20select%20a%20random%20action%20**(exploration)**.%0A%20%20%20%20%20%20%20%20-%20%20With%20probability%20%241%20-%20%5Cvarepsilon%24%2C%20select%20the%20action%20with%20the%20highest%20estimated%20value%3A%20%20%24%5Carg%20%5Cmax_%7Ba%20%5Cin%20A%7D%20Q_t(a)%24%20**(exploitation)**.%0A%20%20%20%202.%20Observe%20the%20reward%20%24R_t(a)%24%0A%20%20%20%203.%20Update%20the%20estimated%20value%20of%20the%20selected%20action%20using%20the%20formula%3A%20%24Q_%7Bt%2B1%7D(a)%20%3D%20Q_t(a)%20%2B%20%5Cfrac%7B1%7D%7BN_a%7D%20(R_t%20-%20Q_t(a))%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(MultiArmedBandit)%3A%0A%20%20%20%20class%20Agent%3A%0A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20problem%3A%20MultiArmedBandit)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.problem%20%3D%20problem%0A%20%20%20%20%20%20%20%20%20%20%20%20self.rewards%20%3D%20np.zeros(problem.k)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.action_counts%20%3D%20np.zeros(problem.k)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.q_values%20%3D%20np.zeros(problem.k)%0A%0A%0A%20%20%20%20class%20EpsilonGreedy(Agent)%3A%0A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20problem%3A%20MultiArmedBandit%2C%20epsilon%3D0.1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20super().__init__(problem)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.epsilon%20%3D%20epsilon%0A%0A%20%20%20%20%20%20%20%20def%20select_action(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20np.random.rand()%20%3C%20self.epsilon%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20np.random.randint(self.problem.k)%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%20return%20np.argmax(self.q_values)%0A%0A%20%20%20%20%20%20%20%20def%20run(self%2C%20steps%3D1000)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20all_rewards%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_%20in%20range(steps)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20action%20%3D%20self.select_action()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20reward%20%3D%20self.problem.arms%5Baction%5D.pull()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20all_rewards.append(reward)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.action_counts%5Baction%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.rewards%5Baction%5D%20%2B%3D%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.q_values%5Baction%5D%20%2B%3D%20(1%20%2F%20self.action_counts%5Baction%5D)%20*%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20reward%20-%20self.q_values%5Baction%5D%0A%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%20return%20all_rewards%0A%20%20%20%20return%20Agent%2C%20EpsilonGreedy%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Now%20that%20the%20%24%5Cvarepsilon%24-greedy%20algorithm%20is%20implemented%2C%20we%20can%20run%20it%20on%20the%20multi-armed%20bandit%20problem%20and%20visualize%20the%20average%20reward%20over%20time.%0A%0A%20%20%20%20We%20will%20use%20different%20values%20of%20%24%5Cvarepsilon%24%20to%20see%20how%20it%20affects%20the%20performance%20of%20the%20algorithm.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(EpsilonGreedy%2C%20bandit)%3A%0A%20%20%20%20n_runs%20%3D%201000%0A%20%20%20%20steps%20%3D%203000%0A%20%20%20%20epsilon_values%20%3D%20%5B0.01%2C%200.1%2C%200.2%5D%0A%20%20%20%20total_rewards_epsilon%20%3D%20np.zeros((len(epsilon_values)%2C%20n_runs%2C%20steps))%0A%20%20%20%20for%20_i%2C%20epsilon_value%20in%20enumerate(epsilon_values)%3A%0A%20%20%20%20%20%20%20%20for%20_n_run%20in%20range(n_runs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_learner%20%3D%20EpsilonGreedy(problem%3Dbandit%2C%20epsilon%3Depsilon_value)%0A%20%20%20%20%20%20%20%20%20%20%20%20_rew%20%3D%20_learner.run(steps%3Dsteps)%0A%20%20%20%20%20%20%20%20%20%20%20%20total_rewards_epsilon%5B_i%2C%20_n_run%5D%20%3D%20np.array(_rew)%0A%20%20%20%20return%20epsilon_values%2C%20n_runs%2C%20steps%2C%20total_rewards_epsilon%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(n_runs%2C%20plot_epsilon)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20Below%2C%20we%20plot%20the%20average%20reward%20over%20time%2C%20computed%20over%20%7Bn_runs%7D%20runs%20for%20different%20%24%5Cvarepsilon%24%20values.%0A%0A%20%20%20%20We%20can%20clearly%20see%20the%20trade-off%20between%20exploration%20and%20exploitation%20in%20the%20graph%20below.%0A%0A%20%20%20%20-%20A%20high%20value%20of%20%24%5Cvarepsilon%24%20makes%20the%20agent%20**explore**%20faster%2C%20since%20suboptimal%20actions%20are%20chosen%20more%20often.%20The%20agent%20quickly%20discovers%20the%20optimal%20action%2C%20but%20continues%20to%20explore%20suboptimal%20actions%2C%20which%20lowers%20the%20average%20reward.%20Asymptotically%2C%20the%20optimal%20action%20will%20be%20selected%20with%20a%20probability%20of%20%241%20-%20%5Cvarepsilon%24.%0A%20%20%20%20-%20A%20low%20value%20of%20%24%5Cvarepsilon%24%20makes%20the%20agent%20**exploit**%20more%2C%20since%20the%20optimal%20action%20is%20selected%20more%20often.%20However%2C%20the%20agent%20may%20take%20longer%20to%20discover%20the%20optimal%20action.%0A%0A%20%20%20%20%7Bmo.as_html(plot_epsilon())%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Optimistic%20initialization%0A%0A%20%20%20%20A%20way%20to%20encourage%20exploration%20is%20to%20initialize%20the%20action%20values%20%24Q_0(a)%24%20to%20high%20values%2C%20higher%20than%20the%20true%20action%20values.%20At%20the%20beginning%20of%20the%20search%2C%20the%20agent%20is%20encouraged%20to%20explore%20all%20actions%2C%20since%20they%20all%20appear%20to%20be%20better%20than%20they%20actually%20are.%0A%0A%20%20%20%20As%20the%20search%20progresses%2C%20the%20action%20values%20converge%20to%20their%20true%20values%2C%20and%20the%20agent%20exploits%20the%20best%20action.%0A%0A%20%20%20%20*Note%3A%20optimistic%20initialization%20is%20extremely%20unsuited%20to%20non-stationary%20problems.*%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(EpsilonGreedy%2C%20MultiArmedBandit)%3A%0A%20%20%20%20class%20OptimisticEpsilonGreedy(EpsilonGreedy)%3A%0A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20problem%3A%20MultiArmedBandit%2C%20epsilon%3D0.1%2C%20initial_value%3D5.0)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20super().__init__(problem%2C%20epsilon)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.q_values%20%3D%20np.ones(problem.k)%20*%20initial_value%0A%20%20%20%20return%20(OptimisticEpsilonGreedy%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Let's%20run%20the%20optimistic%20%24%5Cvarepsilon%24-greedy%20algorithm%20with%20different%20initial%20values%20and%20compare%20it%20to%20the%20standard%20%24%5Cvarepsilon%24-greedy%20algorithm.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(OptimisticEpsilonGreedy%2C%20bandit%2C%20n_runs)%3A%0A%20%20%20%20initial_values%20%3D%20%5B0.0%2C%200.5%2C%205.0%5D%0A%20%20%20%20steps_opt%20%3D%201000%0A%20%20%20%20total_rewards_optimistic%20%3D%20np.zeros((len(initial_values)%2C%20n_runs%2C%20steps_opt))%0A%20%20%20%20for%20_i%2C%20initial_value%20in%20enumerate(initial_values)%3A%0A%20%20%20%20%20%20%20%20for%20_n_run%20in%20range(n_runs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_learner%20%3D%20OptimisticEpsilonGreedy(problem%3Dbandit%2C%20epsilon%3D0.01%2C%20initial_value%3Dinitial_value)%0A%20%20%20%20%20%20%20%20%20%20%20%20_rew%20%3D%20_learner.run(steps%3Dsteps_opt)%0A%20%20%20%20%20%20%20%20%20%20%20%20total_rewards_optimistic%5B_i%2C%20_n_run%5D%20%3D%20np.array(_rew)%0A%20%20%20%20return%20initial_values%2C%20steps_opt%2C%20total_rewards_optimistic%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(n_runs%2C%20plot_optimistic)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20Below%2C%20we%20plot%20the%20average%20reward%20over%20time%2C%20computed%20over%20%7Bn_runs%7D%20runs%20for%20different%20%24Q_0%24%20values.%0A%20%20%20%20We%20can%20see%20that%20optimistic%20initialization%20allows%20the%20agent%20to%20explore%20more%20at%20the%20beginning%20of%20the%20search%2C%20leading%20to%20a%20faster%20discovery%20of%20the%20optimal%20action.%0A%0A%20%20%20%20%7Bmo.as_html(plot_optimistic())%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Upper%20Confidence%20Bound%20(UCB)%20action%20selection%0A%0A%20%20%20%20The%20UCB%20algorithm%20is%20another%20way%20to%20balance%20exploration%20and%20exploitation.%20It%20selects%20actions%20based%20on%20both%20their%20estimated%20value%20and%20the%20uncertainty%20of%20that%20estimate.%0A%0A%20%20%20%20Formally%2C%20the%20action%20selection%20is%20performed%20using%20the%20formula%3A%0A%20%20%20%20%24A_t%20%3D%20%5Carg%20%5Cmax_%7Ba%20%5Cin%20A%7D%20%5Cleft(%20Q_t(a)%20%2B%20c%20%5Csqrt%7B%5Cfrac%7B%5Cln%20t%7D%7BN_a(t)%7D%7D%20%5Cright)%24%0A%0A%20%20%20%20where%3A%0A%20%20%20%20-%20%24Q_t(a)%20%3D%20%5Cfrac%7B%5Csum_%7Bi%20%3D%201%7D%5Et%20R_i(a)%7D%7BN_a(t)%7D%24%20is%20the%20estimated%20value%20of%20action%20%24a%24%20at%20time%20%24t%24%0A%20%20%20%20-%20%24c%24%20is%20a%20hyperparameter%20that%20controls%20the%20degree%20of%20exploration%0A%20%20%20%20-%20%24N_a(t)%24%20is%20the%20number%20of%20times%20action%20%24a%24%20has%20been%20selected%20up%20to%20time%20%24t%24%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Agent%2C%20MultiArmedBandit)%3A%0A%20%20%20%20class%20UCB(Agent)%3A%0A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20problem%3A%20MultiArmedBandit%2C%20c%3D2)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20super().__init__(problem)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.c%20%3D%20c%0A%20%20%20%20%20%20%20%20%20%20%20%20self.t%20%3D%200%0A%0A%20%20%20%20%20%20%20%20def%20select_action(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.t%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20ucb_values%20%3D%20self.q_values%20%2B%20self.c%20*%20np.sqrt(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20np.log(self.t)%20%2F%20(self.action_counts%20%2B%201e-5)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20np.argmax(ucb_values)%0A%0A%20%20%20%20%20%20%20%20def%20run(self%2C%20steps%3D1000)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20all_rewards%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_%20in%20range(steps)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20action%20%3D%20self.select_action()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20reward%20%3D%20self.problem.arms%5Baction%5D.pull()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20all_rewards.append(reward)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.action_counts%5Baction%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.rewards%5Baction%5D%20%2B%3D%20reward%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.q_values%5Baction%5D%20%2B%3D%20(1%20%2F%20self.action_counts%5Baction%5D)%20*%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20reward%20-%20self.q_values%5Baction%5D%0A%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%20return%20all_rewards%0A%20%20%20%20return%20(UCB%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Let's%20run%20the%20UCB%20algorithm.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(MultiArmedBandit%2C%20UCB%2C%20n_runs)%3A%0A%20%20%20%20c_values%20%3D%20%5B0.01%2C%201.0%2C%203.0%5D%0A%20%20%20%20steps_ucb%20%3D%202000%0A%20%20%20%20bandit_ucb%20%3D%20MultiArmedBandit(k%3D10%2C%20mu%3D0%2C%20sigma%3D5)%0A%20%20%20%20total_rewards_ucb%20%3D%20np.zeros((len(c_values)%2C%20n_runs%2C%20steps_ucb))%0A%20%20%20%20for%20_i%2C%20c_value%20in%20enumerate(c_values)%3A%0A%20%20%20%20%20%20%20%20for%20_n_run%20in%20range(n_runs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_learner%20%3D%20UCB(problem%3Dbandit_ucb%2C%20c%3Dc_value)%0A%20%20%20%20%20%20%20%20%20%20%20%20_rew%20%3D%20_learner.run(steps%3Dsteps_ucb)%0A%20%20%20%20%20%20%20%20%20%20%20%20total_rewards_ucb%5B_i%2C%20_n_run%5D%20%3D%20np.array(_rew)%0A%20%20%20%20return%20bandit_ucb%2C%20c_values%2C%20steps_ucb%2C%20total_rewards_ucb%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(n_runs%2C%20plot_ucb)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20We%20plot%20the%20average%20reward%20over%20time%2C%20computed%20over%20%7Bn_runs%7D%20runs%20for%20different%20%24C%24%20values.%0A%0A%20%20%20%20We%20can%20see%20the%20impact%20of%20the%20value%20of%20%24C%24%20on%20the%20convergence%20of%20the%20algorithm.%20A%20lower%20value%20of%20%24C%24%20explores%20less%2C%20leading%20to%20faster%20convergence%20but%20potentially%20suboptimal%20performance.%20A%20higher%20value%20of%20%24C%24%20encourages%20more%20exploration%2C%20which%20can%20lead%20to%20better%20long-term%20performance%20but%20slower%20convergence.%0A%0A%20%20%20%20%7Bmo.as_html(plot_ucb())%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Gradient%20bandits%0A%0A%20%20%20%20Gradient%20bandits%20is%20another%20approach%20to%20the%20multi-armed%20bandit%20problem.%20Instead%20of%20estimating%20action%20values%2C%20the%20agent%20maintains%20a%20preference%20for%20each%20action%20and%20updates%20these%20preferences%20based%20on%20the%20received%20rewards.%0A%0A%20%20%20%20This%20is%20useful%20for%20non-stationary%20problems%2C%20where%20the%20true%20action%20values%20change%20over%20time.%0A%0A%20%20%20%20The%20update%20rule%20for%20gradient%20bandits%20is%3A%0A%0A%20%20%20%20-%20For%20the%20selected%20action%20%24A_t%24%3A%0A%20%20%20%20%20%20%24H_%7Bt%2B1%7D(A_t)%20%3D%20H_t(A_t)%20%2B%20%5Calpha%20(R_t%20-%20%5Cbar%7BR%7D_t)(1%20-%20%5Cpi_t(A_t))%24%0A%20%20%20%20-%20For%20all%20other%20actions%20%24a%20%5Cneq%20A_t%24%3A%0A%20%20%20%20%20%20%24H_%7Bt%2B1%7D(a)%20%3D%20H_t(a)%20-%20%5Calpha%20(R_t%20-%20%5Cbar%7BR%7D_t)%20%5Cpi_t(a)%24%0A%0A%20%20%20%20Where%3A%0A%20%20%20%20-%20%24%5Calpha%24%20is%20the%20step-size%20parameter%0A%20%20%20%20-%20%24%5Cbar%7BR%7D_t%24%20is%20the%20average%20reward%20up%20to%20time%20%24t%24%0A%20%20%20%20-%20%24%5Cpi_t(a)%24%20is%20the%20probability%20of%20selecting%20action%20%24a%24%20at%20time%20%24t%24%2C%20computed%20using%20the%20softmax%20function%20on%20the%20preferences.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Agent%2C%20MultiArmedBandit)%3A%0A%20%20%20%20def%20softmax(x)%3A%0A%20%20%20%20%20%20%20%20e_x%20%3D%20np.exp(x%20-%20np.max(x))%0A%20%20%20%20%20%20%20%20return%20e_x%20%2F%20e_x.sum(axis%3D0)%0A%0A%20%20%20%20class%20GradientBandit(Agent)%3A%0A%0A%20%20%20%20%20%20%20%20def%20__init__(self%2C%20problem%3A%20MultiArmedBandit%2C%20alpha%3D0.1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20super().__init__(problem)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.alpha%20%3D%20alpha%0A%20%20%20%20%20%20%20%20%20%20%20%20self.preferences%20%3D%20np.zeros(problem.k)%0A%20%20%20%20%20%20%20%20%20%20%20%20self.average_reward%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20self.t%20%3D%200%0A%0A%20%20%20%20%20%20%20%20def%20select_action(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20probabilities%20%3D%20softmax(self.preferences)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20np.random.choice(np.arange(self.problem.k)%2C%20p%3Dprobabilities)%0A%0A%20%20%20%20%20%20%20%20def%20run(self%2C%20steps%3D1000)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20all_rewards%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_%20in%20range(steps)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20action%20%3D%20self.select_action()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20reward%20%3D%20self.problem.arms%5Baction%5D.pull()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20all_rewards.append(reward)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.t%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.average_reward%20%2B%3D%20(1%20%2F%20self.t)%20*%20(reward%20-%20self.average_reward)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20a%20in%20range(self.problem.k)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20a%20%3D%3D%20action%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.preferences%5Ba%5D%20%2B%3D%20self.alpha%20*%20(reward%20-%20self.average_reward)%20*%20(1%20-%20np.exp(self.preferences%5Ba%5D)%20%2F%20np.sum(np.exp(self.preferences)))%0A%20%20%20%20%20%20%20%20%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%20%20%20%20%20%20%20%20%20self.preferences%5Ba%5D%20-%3D%20self.alpha%20*%20(reward%20-%20self.average_reward)%20*%20(np.exp(self.preferences%5Ba%5D)%20%2F%20np.sum(np.exp(self.preferences)))%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20all_rewards%0A%20%20%20%20return%20(GradientBandit%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Let's%20run%20the%20gradient%20bandit%20algorithm%20with%20different%20alpha%20values.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(GradientBandit%2C%20bandit)%3A%0A%20%20%20%20alpha_values%20%3D%20%5B0.1%2C%200.5%2C%201%5D%0A%20%20%20%20n_runs_gb%20%3D%20100%0A%20%20%20%20steps_gb%20%3D%202000%0A%20%20%20%20total_rewards_gb%20%3D%20np.zeros((len(alpha_values)%2C%20n_runs_gb%2C%20steps_gb))%0A%20%20%20%20for%20_i%2C%20alpha_value%20in%20enumerate(alpha_values)%3A%0A%20%20%20%20%20%20%20%20for%20_n_run%20in%20range(n_runs_gb)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_learner%20%3D%20GradientBandit(problem%3Dbandit%2C%20alpha%3Dalpha_value)%0A%20%20%20%20%20%20%20%20%20%20%20%20_rew%20%3D%20_learner.run(steps%3Dsteps_gb)%0A%20%20%20%20%20%20%20%20%20%20%20%20total_rewards_gb%5B_i%2C%20_n_run%5D%20%3D%20np.array(_rew)%0A%20%20%20%20return%20alpha_values%2C%20steps_gb%2C%20total_rewards_gb%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(plot_gb)%3A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20Below%2C%20we%20plot%20the%20average%20reward%20over%20time%2C%20computed%20over%20100%20runs%20for%20different%20%24%5Calpha%24%20values.%0A%0A%20%20%20%20The%20learning%20rate%20%24%5Calpha%24%20controls%20how%20quickly%20the%20preferences%20are%20updated%20based%20on%20the%20received%20rewards.%0A%20%20%20%20-%20A%20higher%20%24%5Calpha%24%20leads%20to%20faster%20learning%20but%20can%20also%20cause%20instability%0A%20%20%20%20-%20A%20lower%20%24%5Calpha%24%20results%20in%20slower%20learning%20but%20more%20stable%20updates.%0A%0A%20%20%20%20%7Bmo.as_html(plot_gb())%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23Conclusion%0A%0A%20%20%20%20In%20this%20notebook%2C%20we%20explored%20the%20multi-armed%20bandit%20problem%20and%20implemented%20several%20algorithms%20to%20solve%20it%2C%20including%20the%20%24%5Cvarepsilon%24-greedy%20algorithm%2C%20optimistic%20initialization%2C%20UCB%20action%20selection%2C%20and%20gradient%20bandits.%20We%20analyzed%20how%20different%20hyperparameters%20affect%20the%20performance%20of%20each%20algorithm%20and%20visualized%20the%20average%20reward%20over%20time.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(bandit%2C%20epsilon_values%2C%20steps%2C%20total_rewards_epsilon)%3A%0A%20%20%20%20import%20functools%0A%0A%20%20%20%20%40functools.cache%0A%20%20%20%20def%20plot_epsilon()%3A%0A%20%20%20%20%20%20%20%20_f%2C%20_axes%20%3D%20plt.subplots(1%2C%201%2C%20figsize%3D(8%2C%205))%0A%20%20%20%20%20%20%20%20for%20_i%2C%20epsilon_value_%20in%20enumerate(epsilon_values)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg_rewards%20%3D%20total_rewards_epsilon%5B_i%5D.mean(axis%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg_rewards_mean%20%3D%20running_avg(_avg_rewards%2C%20window_size%3D10)%0A%20%20%20%20%20%20%20%20%20%20%20%20_c%20%3D%20sns.color_palette()%5B_i%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_axes.plot(_avg_rewards%2C%20alpha%3D0.4%2C%20color%3D_c)%0A%20%20%20%20%20%20%20%20%20%20%20%20_axes.plot(_avg_rewards_mean%2C%20label%3Df%22%24%5Cepsilon%24%20%3D%20%7Bepsilon_value_%7D%22%2C%20color%3D_c)%0A%20%20%20%20%20%20%20%20_axes.plot(%5Bbandit.arms%5Bnp.argmax(%5Barm.mu%20for%20arm%20in%20bandit.arms%5D)%5D.mu%5D*steps%2C%20'k--'%2C%20label%3D%22Optimal%20action%20value%22%2C%20color%3D'black'%2C%20linewidth%3D0.5)%0A%20%20%20%20%20%20%20%20_axes.set_xlabel(%22Steps%22)%0A%20%20%20%20%20%20%20%20_axes.set_ylabel(%22Average%20reward%22)%0A%20%20%20%20%20%20%20%20plt.title(%22Average%20reward%20evolution%20for%20different%20%24%5Cepsilon%24%20values%22)%0A%20%20%20%20%20%20%20%20plt.legend()%0A%20%20%20%20%20%20%20%20plt.grid(True)%0A%20%20%20%20%20%20%20%20return%20plt.gca()%0A%20%20%20%20return%20functools%2C%20plot_epsilon%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(bandit_ucb%2C%20c_values%2C%20functools%2C%20steps_ucb%2C%20total_rewards_ucb)%3A%0A%20%20%20%20%40functools.cache%0A%20%20%20%20def%20plot_ucb()%3A%0A%20%20%20%20%20%20%20%20_f%2C%20_axes%20%3D%20plt.subplots(1%2C%201%2C%20figsize%3D(8%2C%205))%0A%20%20%20%20%20%20%20%20for%20_i%2C%20c_value_%20in%20enumerate(c_values)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg_rewards%20%3D%20total_rewards_ucb%5B_i%5D.mean(axis%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg_rewards_mean%20%3D%20running_avg(_avg_rewards%2C%20window_size%3D10)%0A%20%20%20%20%20%20%20%20%20%20%20%20_c%20%3D%20sns.color_palette()%5B_i%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_axes.plot(_avg_rewards%2C%20alpha%3D0.4%2C%20color%3D_c)%0A%20%20%20%20%20%20%20%20%20%20%20%20_axes.plot(_avg_rewards_mean%2C%20label%3Df%22%24C%24%20%3D%20%7Bc_value_%7D%22%2C%20color%3D_c)%0A%20%20%20%20%20%20%20%20_axes.plot(%5Bbandit_ucb.arms%5Bnp.argmax(%5Barm.mu%20for%20arm%20in%20bandit_ucb.arms%5D)%5D.mu%5D*steps_ucb%2C%20'k--'%2C%20label%3D%22Optimal%20action%20value%22%2C%20color%3D'black'%2C%20linewidth%3D0.5)%0A%20%20%20%20%20%20%20%20_axes.set_xlabel(%22Steps%22)%0A%20%20%20%20%20%20%20%20_axes.set_ylabel(%22Average%20reward%22)%0A%20%20%20%20%20%20%20%20plt.title(%22Average%20reward%20evolution%20for%20different%20%24C%24%20values%22)%0A%20%20%20%20%20%20%20%20plt.legend()%0A%20%20%20%20%20%20%20%20plt.grid(True)%0A%20%20%20%20%20%20%20%20return%20plt.gca()%0A%20%20%20%20return%20(plot_ucb%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(alpha_values%2C%20bandit%2C%20functools%2C%20steps_gb%2C%20total_rewards_gb)%3A%0A%20%20%20%20%40functools.cache%0A%20%20%20%20def%20plot_gb()%3A%0A%20%20%20%20%20%20%20%20_f%2C%20_axes%20%3D%20plt.subplots(1%2C%201%2C%20figsize%3D(8%2C%205))%0A%20%20%20%20%20%20%20%20for%20_i%2C%20alpha_value_%20in%20enumerate(alpha_values)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg_rewards%20%3D%20total_rewards_gb%5B_i%5D.mean(axis%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg_rewards_mean%20%3D%20running_avg(_avg_rewards%2C%20window_size%3D10)%0A%20%20%20%20%20%20%20%20%20%20%20%20_c%20%3D%20sns.color_palette()%5B_i%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_axes.plot(_avg_rewards%2C%20alpha%3D0.4%2C%20color%3D_c)%0A%20%20%20%20%20%20%20%20%20%20%20%20_axes.plot(_avg_rewards_mean%2C%20label%3Drf%22%24%5Calpha%24%20%3D%20%7Balpha_value_%7D%22%2C%20color%3D_c)%0A%20%20%20%20%20%20%20%20_axes.plot(%5Bbandit.arms%5Bnp.argmax(%5Barm.mu%20for%20arm%20in%20bandit.arms%5D)%5D.mu%5D*steps_gb%2C%20'k--'%2C%20label%3D%22Optimal%20action%20value%22%2C%20color%3D'black'%2C%20linewidth%3D0.5)%0A%20%20%20%20%20%20%20%20_axes.set_xlabel(%22Steps%22)%0A%20%20%20%20%20%20%20%20_axes.set_ylabel(%22Average%20reward%22)%0A%20%20%20%20%20%20%20%20plt.title(r%22Average%20reward%20evolution%20for%20different%20%24%5Calpha%24%20values%22)%0A%20%20%20%20%20%20%20%20plt.legend()%0A%20%20%20%20%20%20%20%20plt.grid(True)%0A%20%20%20%20%20%20%20%20return%20plt.gca()%0A%20%20%20%20return%20(plot_gb%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(bandit%2C%20functools%2C%20initial_values%2C%20steps_opt%2C%20total_rewards_optimistic)%3A%0A%20%20%20%20%40functools.cache%0A%20%20%20%20def%20plot_optimistic()%3A%0A%20%20%20%20%20%20%20%20_f%2C%20_axes%20%3D%20plt.subplots(1%2C%201%2C%20figsize%3D(8%2C%205))%0A%20%20%20%20%20%20%20%20for%20_i%2C%20initial_value_%20in%20enumerate(initial_values)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg_rewards%20%3D%20total_rewards_optimistic%5B_i%5D.mean(axis%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20_avg_rewards_mean%20%3D%20running_avg(_avg_rewards%2C%20window_size%3D10)%0A%20%20%20%20%20%20%20%20%20%20%20%20_c%20%3D%20sns.color_palette()%5B_i%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_axes.plot(_avg_rewards%2C%20alpha%3D0.4%2C%20color%3D_c)%0A%20%20%20%20%20%20%20%20%20%20%20%20_axes.plot(_avg_rewards_mean%2C%20label%3Df%22%24Q_0%24%20%3D%20%7Binitial_value_%7D%22%2C%20color%3D_c)%0A%20%20%20%20%20%20%20%20_axes.plot(%5Bbandit.arms%5Bnp.argmax(%5Barm.mu%20for%20arm%20in%20bandit.arms%5D)%5D.mu%5D*steps_opt%2C%20'k--'%2C%20label%3D%22Optimal%20action%20value%22%2C%20color%3D'black'%2C%20linewidth%3D0.5)%0A%20%20%20%20%20%20%20%20_axes.set_xlabel(%22Steps%22)%0A%20%20%20%20%20%20%20%20_axes.set_ylabel(%22Average%20reward%22)%0A%20%20%20%20%20%20%20%20plt.title(%22Average%20reward%20evolution%20for%20different%20%24Q_0%24%20values%22)%0A%20%20%20%20%20%20%20%20plt.legend()%0A%20%20%20%20%20%20%20%20plt.grid(True)%0A%20%20%20%20%20%20%20%20return%20plt.gca()%0A%20%20%20%20return%20(plot_optimistic%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(functools%2C%20rewards)%3A%0A%20%20%20%20%40functools.cache%0A%20%20%20%20def%20plot_problem()%3A%0A%20%20%20%20%20%20%20%20f%2C%20ax%20%3D%20plt.subplots(1%2C%201%2C%20figsize%3D(8%2C%205))%0A%20%20%20%20%20%20%20%20sns.violinplot(data%3Drewards.T%2C%20ax%3Dax)%0A%20%20%20%20%20%20%20%20plt.grid(True)%0A%20%20%20%20%20%20%20%20plt.title(%22Reward%20distributions%20of%20each%20arm%22)%0A%20%20%20%20%20%20%20%20plt.xlabel(%22Arm%22)%0A%20%20%20%20%20%20%20%20plt.ylabel(%22Reward%22)%0A%20%20%20%20%20%20%20%20return%20plt.gca()%0A%20%20%20%20return%20(plot_problem%2C)%0A%0A%0A%40app.cell%0Adef%20_()%3A%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
406404cfc97d796b35e28412b09bb701