import%20marimo%0A%0A__generated_with%20%3D%20%220.9.3%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__()%3A%0A%20%20%20%20import%20marimo%20as%20mo%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Multi-armed%20bandit%20competition%0A%0A%20%20%20%20%20%20%20%20Nessa%20competi%C3%A7%C3%A3o%20voc%C3%AA%20dever%C3%A1%20implementar%20uma%20estrat%C3%A9gia%20a%20ser%20seguida%20por%20um%20agente%20que%20enfrenta%20o%20problema%20do%20bandido%20multi-bra%C3%A7o%3B%20quanto%20melhor%20for%20sua%20estrat%C3%A9gia%2C%20maior%20ser%C3%A1%20o%20payoff%20obtido.%0A%0A%20%20%20%20%20%20%20%20Primeiro%20falaremos%20das%20regras%20da%20competi%C3%A7%C3%A3o%3B%20para%20entender%20o%20problema%20em%20si%2C%20leia%20este%20documento%20at%C3%A9%20o%20final.%0A%0A%20%20%20%20%20%20%20%20A%20competi%C3%A7%C3%A3o%20de%20multi-armed%20bandits%20ter%C3%A1%20as%20seguintes%20regras%3A%0A%0A%20%20%20%20%20%20%20%20-%20Cada%20participante%20deve%20submeter%20uma%20estrat%C3%A9gia%20na%20forma%20de%20uma%20fun%C3%A7%C3%A3o%20Python%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20A%20estrat%C3%A9gia%20deve%20ter%20os%20mesmos%20par%C3%A2metros%20e%20retornos%20dos%20exemplos%20mostrados%20abaixo%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Use%20a%20fun%C3%A7%C3%A3o%20%60simulate_turns%60%20provida%20para%20testar%20suas%20implementa%C3%A7%C3%B5es%3B%0A%20%20%20%20%20%20%20%20-%20Todas%20as%20fun%C3%A7%C3%B5es%20devem%20se%20comportar%20corretamente%3A%20receber%20e%20retornar%20valores%20v%C3%A1lidos%20dos%20tipos%20esperados%3B%0A%20%20%20%20%20%20%20%20-%20Haver%C3%A1%20pr%C3%AAmios%20para%20as%20melhores%20estrat%C3%A9gias%3B%0A%20%20%20%20%20%20%20%20%22%22%22%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Das%20estrat%C3%A9gias%0A%0A%20%20%20%20%20%20%20%20-%20As%20estrat%C3%A9gias%20devem%20ser%20fun%C3%A7%C3%B5es%20de%20dois%20par%C3%A2metros%20(n%C3%BAmero%20de%20bra%C3%A7os%20e%20n%C3%BAmero%20de%20turnos)%2C%20que%20retornam%20uma%20fun%C3%A7%C3%A3o%20que%20escolhe%20um%20bra%C3%A7o%20a%20ser%20jogado%20em%20um%20turno%20com%20base%20no%20hist%C3%B3rico%20de%20payoffs%20at%C3%A9%20aquele%20turno%20e%20o%20n%C3%BAmero%20de%20turnos%20restantes%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20-%20Se%20a%20sua%20estrat%C3%A9gia%20n%C3%A3o%20depende%20do%20n%C3%BAmero%20de%20bra%C3%A7os%20ou%20do%20n%C3%BAmero%20de%20turnos%20voc%C3%AA%20pode%20ignorar%20os%20argumentos%20correspondentes%2C%20mas%20a%20fun%C3%A7%C3%A3o%20deve%20aceit%C3%A1-los%3B%0A%20%20%20%20%20%20%20%20%22%22%22%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Dos%20rankings%0A%0A%20%20%20%20%20%20%20%20-%20As%20estrat%C3%A9gias%20submetidas%20ser%C3%A3o%20ranqueadas%20de%20acordo%20com%20os%20maiores%20payoffs%20m%C3%A9dios%20em%20tr%C3%AAs%20rodadas%20de%2050%2C%20200%2C%20e%201000%20turnos%3B%0A%20%20%20%20%20%20%20%20%22%22%22%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Da%20submiss%C3%A3o%0A%0A%20%20%20%20%20%20%20%20Cada%20competidor%20deve%20subir%20no%20eclass%20um%20arquivo%20python%20%60submission-SEUNOME.py%60%20com%20a%20estrat%C3%A9gia%20a%20ser%20submetida%2C%20nos%20moldes%20abaixo.%20Certifique-se%20de%20usar%20o%20nome%20de%20fun%C3%A7%C3%A3o%20correto%20(o%20mesmo%20da%20fun%C3%A7%C3%A3o%20abaixo).%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__()%3A%0A%20%20%20%20def%20strategy(num_arms%2C%20num_turns)%3A%0A%20%20%20%20%20%20%20%20def%20choose_arm(payoff_history%2C%20remaining_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20...%0A%20%20%20%20%20%20%20%20return%20choose_arm%0A%20%20%20%20return%20(strategy%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20O%20problema%20do%20bandido%20multi-bra%C3%A7o%0A%0A%20%20%20%20%20%20%20%20O%20problema%20do%20bandido%20multi-bra%C3%A7o%20(_multi-armed%20bandit_)%20tem%20sua%20origem%20no%20nome%20dado%20%C3%A0s%20m%C3%A1quinas%20de%20cassino%20conhecidas%20como%20%5Bca%C3%A7a-n%C3%ADqueis%5D(https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2Fb%2Fbf%2FAntique_one-armed_bandit%252C_Ventnor%252C_Isle_of_Wight%252C_UK.jpg%2F800px-Antique_one-armed_bandit%252C_Ventnor%252C_Isle_of_Wight%252C_UK.jpg)%20em%20portugu%C3%AAs%20e%20%E2%80%98one-armed%20bandits%E2%80%99%20em%20ingl%C3%AAs.%20Estilizadamente%2C%20o%20problema%20%C3%A9%20o%20seguinte%3A%20uma%20pessoa%20entra%20num%20cassino%20com%20dinheiro%20para%20%24T%24%20jogos%20em%20ca%C3%A7a-n%C3%ADqueis.%20Os%20ca%C3%A7a-n%C3%ADqueis%20n%C3%A3o%20s%C3%A3o%20todos%20iguais%3A%20cada%20ca%C3%A7a-n%C3%ADquel%20tem%20uma%20distribui%C3%A7%C3%A3o%20de%20probabilidade%20das%20recompensas%20diferente.%20Como%20o%20jogador%20deve%20escolher%20os%20ca%C3%A7a-n%C3%ADqueis%20de%20modo%20a%20maximizar%20sua%20recompensa%3F%0A%0A%20%20%20%20%20%20%20%20**Obs.**%3A%20Neste%20texto%2C%20vamos%20chamar%20os%20ca%C3%A7a-n%C3%ADqueis%20de%20_bra%C3%A7os_%2C%20seguindo%20a%20nomenclatura%20usual%20do%20problema%20em%20ingl%C3%AAs.%0A%0A%20%20%20%20%20%20%20%20A%20distribui%C3%A7%C3%A3o%20de%20recompensas%20dos%20bra%C3%A7os%2Fca%C3%A7a-n%C3%ADqueis%20pode%20ser%20uniforme%20de%20zero%20a%20%242E%24%2C%20por%20exemplo%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__()%3A%0A%20%20%20%20import%20random%20as%20rd%0A%20%20%20%20return%20(rd%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(rd)%3A%0A%20%20%20%20%23%0A%20%20%20%20rd.seed(87783935059799365746542525305988445192443132548924425046405794185197484867163137815156603533304919212757733573730384968533289518668485508333473047571782437488122365766536586699093266741116219881646284852036905060215472325428462073968643194920571720487062787315593065299098399942850029350124901832752177378071)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__(rd)%3A%0A%20%20%20%20def%20uniform_arm(E)%3A%0A%20%20%20%20%20%20%20%20return%20lambda%3A%20rd.uniform(0%2C%202%20*%20E)%0A%20%20%20%20return%20(uniform_arm%2C)%0A%0A%0A%40app.cell%0Adef%20__(uniform_arm)%3A%0A%20%20%20%20ua%20%3D%20uniform_arm(E%3D10)%0A%20%20%20%20%23%20esses%20valores%20representariam%20os%20payoffs%20do%20jogador%3A%0A%20%20%20%20%5Bua()%20for%20_%20in%20range(10)%5D%0A%20%20%20%20return%20(ua%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Programamos%20um%20bra%C3%A7o%20do%20bandido%20como%20uma%20fun%C3%A7%C3%A3o%2C%20que%20nos%20d%C3%A1%20uma%20recompensa%20a%20cada%20vez%20que%20ela%20%C3%A9%20invocada.%0A%0A%20%20%20%20%20%20%20%20Segue%20um%20outro%20exemplo%20de%20um%20bra%C3%A7o%20de%20bandido%2C%20em%20que%20o%20payoff%20%C3%A9%20uma%20vari%C3%A1vel%20de%20bernoulli%20se%20%24E%20%5Cin%20(0%2C%201)%24.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__(rd)%3A%0A%20%20%20%20def%20bernoulli_arm(E)%3A%0A%20%20%20%20%20%20%20%20if%20E%20%3E%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20E%20%3D%201%0A%20%20%20%20%20%20%20%20elif%20E%20%3C%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20E%20%3D%200%0A%20%20%20%20%20%20%20%20return%20lambda%3A%201%20if%20rd.random()%20%3C%20E%20else%200%0A%20%20%20%20return%20(bernoulli_arm%2C)%0A%0A%0A%40app.cell%0Adef%20__(bernoulli_arm)%3A%0A%20%20%20%20ba%20%3D%20bernoulli_arm(E%3D0.4)%0A%20%20%20%20%5Bba()%20for%20_%20in%20range(10)%5D%0A%20%20%20%20return%20(ba%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20J%C3%A1%20uma%20pessoa%20jogadora%20(ou%20agente%2C%20ou%20algoritmo%2C%20ou%20estrat%C3%A9gia)%20pode%20ser%20programada%20como%20uma%20fun%C3%A7%C3%A3o%20que%20escolhe%20o%20pr%C3%B3ximo%20bra%C3%A7o%20(ca%C3%A7a-n%C3%ADquel)%20a%20ser%20jogado%2C%20dado%20o%20hist%C3%B3rico%20das%20jogadas%2Frecompensas%20anteriores%20e%20o%20n%C3%BAmero%20de%20rodadas%20faltantes%20como%20par%C3%A2metros.%0A%0A%20%20%20%20%20%20%20%20**Essa%20%C3%A9%20a%20fun%C3%A7%C3%A3o%20que%20voc%C3%AAs%20devem%20implementar.**%0A%0A%20%20%20%20%20%20%20%20Vamos%20identificar%20os%20bra%C3%A7os%20por%20seus%20%C3%ADndices%20na%20lista%20do%20hist%C3%B3rico%20de%20jogadas.%20Por%20exemplo%2C%20o%20hist%C3%B3rico%20%60%5B%5B10%2C%205.5%5D%2C%20%5B6.28%5D%2C%20%5B%5D%5D%60%20indica%20que%20o%20bra%C3%A7o%200%20j%C3%A1%20foi%20jogado%202%20vezes%2C%20dando%20payoffs%20de%2010%20e%20de%205.5%2C%20ao%20passo%20que%20o%20bra%C3%A7o%202%20nunca%20foi%20jogado%2C%20e%20o%20bra%C3%A7o%201%20foi%20jogado%20uma%20vez%20e%20teve%20payoff%20de%206.28.%0A%0A%20%20%20%20%20%20%20%20Uma%20estrat%C3%A9gia%20simples%20de%20ser%20implementada%20%C3%A9%20aquela%20que%20escolhe%20o%20bra%C3%A7o%20a%20ser%20jogado%20de%20forma%20aleat%C3%B3ria%20a%20cada%20rodada%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__(rd)%3A%0A%20%20%20%20def%20pick_random(num_arms%2C%20num_turns)%3A%0A%20%20%20%20%20%20%20%20def%20choose(payoff_history%2C%20remaining_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20rd.randrange(num_arms)%0A%20%20%20%20%20%20%20%20return%20choose%0A%20%20%20%20return%20(pick_random%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22Uma%20outra%20estrat%C3%A9gia%20simples%20de%20ser%20programada%20%C3%A9%20aquela%20que%20faz%20um%20rod%C3%ADzio%20entre%20os%20bra%C3%A7os%2C%20ignorando%20as%20recompensas%20recebidas.%20Chamamos%20essa%20estrat%C3%A9gia%20de%20*round%20robin*%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__()%3A%0A%20%20%20%20def%20sua_round_robin(num_arms%2C%20num_turns)%3A%0A%20%20%20%20%20%20%20%20def%20choose(payoff_history%2C%20remaining_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20...%20%23%20tente%20implement%C3%A1-la%20aqui%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20deve%20retornar%20um%20id%20de%20bra%C3%A7o%20(inteiro%20in%20range(num_arms))%0A%20%20%20%20%20%20%20%20return%20choose%0A%20%20%20%20return%20(sua_round_robin%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__()%3A%0A%20%20%20%20%23%20solu%C3%A7%C3%A3o%0A%20%20%20%20def%20round_robin(num_arms%2C%20num_turnos)%3A%0A%20%20%20%20%20%20%20%20def%20choose(payoff_history%2C%20remaining_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20faz%20um%20rod%C3%ADzio%20dos%20ids%20de%20bra%C3%A7o%20de%20acordo%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20com%20o%20n%C3%BAmero%20de%20turnos%20remanescentes.%20H%C3%A1%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20outras%20formas%20de%20implementar%20essa%20estrat%C3%A9gia%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20remaining_turns%20%25%20len(payoff_history)%0A%20%20%20%20%20%20%20%20return%20choose%0A%20%20%20%20return%20(round_robin%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22Note%20que%20a%20estrat%C3%A9gia%20%60round_robin%60%20n%C3%A3o%20faz%20uso%20das%20informa%C3%A7%C3%B5es%20de%20n%C3%BAmero%20total%20de%20turnos%20ou%20do%20n%C3%BAmero%20de%20bra%C3%A7os%2C%20mas%20outras%20estrat%C3%A9gias%20podem%20escolher%20faz%C3%AA-lo.%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%22Podemos%20simular%20%24T%24%20jogadas%20segundo%20uma%20estrat%C3%A9gia%20com%20a%20seguinte%20fun%C3%A7%C3%A3o%2C%20que%20nos%20retorna%20o%20payoff%20obtido%2C%20e%20algumas%20estat%C3%ADsticas%20sobre%20a%20estrat%C3%A9gia%20adotada%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__()%3A%0A%20%20%20%20def%20simulate_turns(arms%2C%20nturns%2C%20strategy_fn)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Retorna%20o%20payoff%20total%20obtido%20pela%20estrat%C3%A9gia%20obtida%20pela%20chamada%20strategy_fn(K%2C%20nturns)%2C%20em%20que%20K%20%C3%A9%20o%20n%C3%BAmero%20de%20bra%C3%A7os%2C%20e%20os%20bra%C3%A7os%20s%C3%A3o%20aqueles%20esquecificados%20pelo%20argumento%20arms%2C%20ao%20longo%20de%20nturns%20turnos.%0A%20%20%20%20%20%20%20%20Retorna%20tamb%C3%A9m%20estat%C3%ADsticas%20b%C3%A1sicas%20sobre%20cada%20bra%C3%A7o%3A%20seu%20payoff%20m%C3%A9dio%20ao%20longo%20dos%20turnos%2C%20e%20quantas%20vezes%20ele%20foi%20escolhido%20pela%20estrat%C3%A9gia.%22%22%22%0A%20%20%20%20%20%20%20%20K%20%3D%20len(arms)%0A%20%20%20%20%20%20%20%20payoff_history%20%3D%20%5B%5B%5D%20for%20_%20in%20range(K)%5D%0A%20%20%20%20%20%20%20%20strategy%20%3D%20strategy_fn(K%2C%20nturns)%0A%20%20%20%20%20%20%20%20for%20t%20in%20range(nturns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20arm_id%20%3D%20strategy(payoff_history%2C%20nturns%20-%20t)%0A%20%20%20%20%20%20%20%20%20%20%20%20payoff%20%3D%20arms%5Barm_id%5D()%20%23%20invoca%20o%20bra%C3%A7o%20e%20decide%20o%20payoff%0A%20%20%20%20%20%20%20%20%20%20%20%20payoff_history%5Barm_id%5D.append(payoff)%0A%20%20%20%20%20%20%20%20return%20sum(map(sum%2C%20payoff_history))%2C%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20strategy_stats(payoff_history)%0A%0A%20%20%20%20def%20strategy_stats(payoff_history)%3A%0A%20%20%20%20%20%20%20%20def%20arm_stats(payoffs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20n%20%3D%20len(payoffs)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20n%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20dict(nchosen%3Dn%2C%20avg_payoff%3Dsum(payoffs)%2Fn)%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%20dict(nchosen%3D0%2C%20avg_payoff%3D0)%0A%20%20%20%20%20%20%20%20return%20%5Barm_stats(arm_payoffs)%20for%20arm_payoffs%20in%20payoff_history%5D%0A%20%20%20%20return%20simulate_turns%2C%20strategy_stats%0A%0A%0A%40app.cell%0Adef%20__(pick_random%2C%20simulate_turns%2C%20uniform_arm)%3A%0A%20%20%20%20T%20%3D%2020%0A%20%20%20%20simulate_turns(%0A%20%20%20%20%20%20%20%20%23%20bra%C3%A7os%20com%20payoff%20esperado%20de%2010%20a%20100%0A%20%20%20%20%20%20%20%20%5Buniform_arm(10%20*%20i%20%2B%2010)%20for%20i%20in%20range(10)%5D%2C%0A%20%20%20%20%20%20%20%20T%2C%0A%20%20%20%20%20%20%20%20pick_random%0A%20%20%20%20)%0A%20%20%20%20return%20(T%2C)%0A%0A%0A%40app.cell%0Adef%20__(T%2C%20round_robin%2C%20simulate_turns%2C%20uniform_arm)%3A%0A%20%20%20%20simulate_turns(%0A%20%20%20%20%20%20%20%20%23%20bra%C3%A7os%20com%20payoff%20esperado%20de%2010%20a%20100%0A%20%20%20%20%20%20%20%20%5Buniform_arm(10%20*%20i%20%2B%2010)%20for%20i%20in%20range(10)%5D%2C%0A%20%20%20%20%20%20%20%20T%2C%0A%20%20%20%20%20%20%20%20round_robin%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%22Uma%20outra%20estrat%C3%A9gia%20poss%C3%ADvel%20%C3%A9%20testar%20cada%20bra%C3%A7o%20uma%20vez%2C%20e%20nas%20rodadas%20seguintes%20escolher%20o%20bra%C3%A7o%20que%20tem%20maior%20payoff%20m%C3%A9dio%3A%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__()%3A%0A%20%20%20%20def%20sua_explore_once(num_arms%2C%20num_turnos)%3A%0A%20%20%20%20%20%20%20%20def%20choose(payoff_history%2C%20rem_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20...%20%23%20tente%20voc%C3%AA%20mesmo%0A%20%20%20%20%20%20%20%20return%20choose%0A%20%20%20%20return%20(sua_explore_once%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__()%3A%0A%20%20%20%20%23%20solu%C3%A7%C3%A3o%0A%20%20%20%20def%20idx_maxpayoff(iterable)%3A%0A%20%20%20%20%20%20%20%20%23%20retorna%20o%20%C3%ADndice%20do%20bra%C3%A7o%20de%20maior%20payoff%20m%C3%A9dio%0A%20%20%20%20%20%20%20%20def%20avg_payoff(payoffs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20n%20%3D%20len(payoffs)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20sum(payoffs)%20%2F%20n%20if%20n%20%3E%200%20else%200%20%20%0A%20%20%20%20%20%20%20%20return%20max(range(len(iterable))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20key%3Dlambda%20i%3A%20avg_payoff(iterable%5Bi%5D))%0A%0A%20%20%20%20def%20explore_once(num_arms%2C%20num_turnos)%3A%0A%20%20%20%20%20%20%20%20def%20choose(payoff_history%2C%20rem_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20rem_turns%20%3E%20num_turnos%20-%20num_arms%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20se%20ainda%20n%C3%A3o%20tivemos%20num_arms%20turnos%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20fazemos%20round%20robin%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20rem_turns%20%25%20num_arms%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%20%23%20se%20j%C3%A1%20exploramos%20uma%20vez%2C%20escolhemos%20bra%C3%A7o%20de%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20maior%20payoff%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_arm%20%3D%20idx_maxpayoff(payoff_history)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20best_arm%0A%20%20%20%20%20%20%20%20return%20choose%0A%20%20%20%20return%20explore_once%2C%20idx_maxpayoff%0A%0A%0A%40app.cell%0Adef%20__(explore_once%2C%20round_robin%2C%20simulate_turns%2C%20uniform_arm)%3A%0A%20%20%20%20nturns%20%3D%20200%0A%0A%20%20%20%20round_robin_returns%20%3D%20simulate_turns(%0A%20%20%20%20%20%20%20%20%5Buniform_arm(10%20*%20i%20%2B%2010)%20for%20i%20in%20range(10)%5D%2C%0A%20%20%20%20%20%20%20%20nturns%2C%0A%20%20%20%20%20%20%20%20round_robin%0A%20%20%20%20)%0A%20%20%20%20explore_once_returns%20%3D%20simulate_turns(%0A%20%20%20%20%20%20%20%20%5Buniform_arm(10%20*%20i%20%2B%2010)%20for%20i%20in%20range(10)%5D%2C%0A%20%20%20%20%20%20%20%20nturns%2C%0A%20%20%20%20%20%20%20%20explore_once%0A%20%20%20%20)%0A%20%20%20%20round_robin_returns%2C%20explore_once_returns%0A%20%20%20%20return%20explore_once_returns%2C%20nturns%2C%20round_robin_returns%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Naturalmente%2C%20testar%20cada%20bra%C3%A7o%20apenas%20uma%20vez%20nos%20d%C3%A1%20informa%C3%A7%C3%A3o%20altamente%20incerta%20sobre%20a%20distribui%C3%A7%C3%A3o%20de%20recompensas%20de%20cada%20um.%20Poder%C3%ADamos%20test%C3%A1-los%20v%C3%A1rias%20vezes%20antes%20de%20escolhermos%20o%20melhor%20bandido%20encontrado%2C%20mas%20temos%20um%20tradeoff%3A%20quando%20mais%20escolhemos%20explorar%20_(explore)_%2C%20menos%20podemos%20explorar%20_(exploit)_.%20Esse%20%C3%A9%20o%20tradeoff%20conhecido%20como%20o%20%5B*exploration-exploitation%20dilemma*%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FExploration-exploitation_dilemma).%0A%0A%20%20%20%20%20%20%20%20Ao%20projetar%20a%20sua%20estrat%C3%A9gia%2C%20leve%20em%20conta%20esse%20dilema.%20Use%20os%20exemplos%20%60round_robin%60%20e%20%60explore_once%60%20para%20criar%20sua%20pr%C3%B3pria%20estrat%C3%A9gia%2C%20al%C3%A9m%20daqueles%20explorados%20nos%20exerc%C3%ADcios%20abaixo.%0A%20%20%20%20%20%20%20%20%22%22%22%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20Seguem%20alguns%20exerc%C3%ADcios%20para%20treino%20antes%20da%20competi%C3%A7%C3%A3o.%0A%0A%20%20%20%20%20%20%20%20%23%20Exerc%C3%ADcios%0A%20%20%20%20%20%20%20%20%22%22%22%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(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%23%20Ex.%20explore-first%0A%0A%20%20%20%20%20%20%20%20Generalize%20a%20fun%C3%A7%C3%A3o%20%60explore_once%60%20de%20modo%20a%20testar%20cada%20bra%C3%A7o%20%24n%24%20vezes%20antes%20de%20escolher%20o%20melhor%20bra%C3%A7o%20encontrado%20e%20explor%C3%A1-lo%20at%C3%A9%20o%20fim%20das%20rodadas.%20%24n%24%20deve%20ser%20escolhido%20pela%20fun%C3%A7%C3%A3o%20com%20base%20no%20n%C3%BAmero%20de%20bra%C3%A7os%20e%20no%20n%C3%BAmero%20de%20rodadas.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__()%3A%0A%20%20%20%20def%20sua_explore_first(narms%2C%20nturns)%3A%0A%20%20%20%20%20%20%20%20def%20explore_ntimes(payoff_history%2C%20remaining_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20...%0A%20%20%20%20%20%20%20%20return%20explore_ntimes%0A%20%20%20%20return%20(sua_explore_first%2C)%0A%0A%0A%40app.cell%0Adef%20__(explore_first%2C%20simulate_turns%2C%20uniform_arm)%3A%0A%20%20%20%20_T%20%3D%20200%0A%20%20%20%20simulate_turns(%0A%20%20%20%20%20%20%20%20%5Buniform_arm(10%20*%20i%20%2B%2010)%20for%20i%20in%20range(10)%5D%2C%0A%20%20%20%20%20%20%20%20_T%2C%0A%20%20%20%20%20%20%20%20explore_first%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(idx_maxpayoff)%3A%0A%20%20%20%20%23%20solu%C3%A7%C3%A3o%0A%20%20%20%20import%20math%0A%20%20%20%20def%20explore_first(narms%2C%20nturns)%3A%0A%20%20%20%20%20%20%20%20%23%20existem%20v%C3%A1rias%20outras%20formas%20de%20escolher%20n%0A%20%20%20%20%20%20%20%20n%20%3D%20math.floor(0.1%20*%20nturns)%0A%20%20%20%20%20%20%20%20def%20explore_ntimes(payoff_history%2C%20remaining_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20nonlocal%20n%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20n%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20n%20-%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20remaining_turns%20%25%20narms%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%20idx_maxpayoff(payoff_history)%0A%20%20%20%20%20%20%20%20return%20explore_ntimes%0A%20%20%20%20return%20explore_first%2C%20math%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%23%20Ex.%20%24%5Cepsilon%24-greedy%0A%0A%20%20%20%20%20%20%20%20Uma%20cr%C3%ADtica%20comum%20%C3%A0%20estrat%C3%A9gias%20do%20tipo%20%60explore_first%60%20%C3%A9%20que%20elas%20tem%20p%C3%A9ssima%20performance%20nos%20turnos%20iniciais%20do%20jogo.%20Uma%20forma%20de%20melhorar%20isso%20sem%20abrir%20m%C3%A3o%20da%20*exploration*%20%C3%A9%20definir%20%24%5Cepsilon_t%24%20para%20cada%20rodada%2C%20e%20escolher%20*exploration*%20com%20probabilidade%20%24%5Cepsilon_t%24%2C%20e%20escolher%20*exploitation*%20nos%20outros%20casos%20(em%20que%20*exploitation*%20%C3%A9%20escolher%20o%20melhor%20bra%C3%A7o%20encontrado%20at%C3%A9%20o%20turno%20corrente).%20%24%5Cepsilon_t%24%20pode%20ser%20fixo%2C%20mas%20idealmente%20ele%20deve%20variar%20(como%3F).%0A%0A%20%20%20%20%20%20%20%20Qual%20%C3%A9%20o%20outro%20problema%20resolvido%20por%20essa%20estrat%C3%A9gia%2C%20em%20rela%C3%A7%C3%A3o%20%C3%A0s%20estrat%C3%A9gias%20do%20tipo%20*explore-first*%3F%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20__()%3A%0A%20%20%20%20def%20sua_epsilon_greedy(narms%2C%20nturns)%3A%0A%20%20%20%20%20%20%20%20def%20choose(payoff_history%2C%20rem_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%20%20%20%20%20%20%20%20return%20choose%0A%20%20%20%20return%20(sua_epsilon_greedy%2C)%0A%0A%0A%40app.cell%0Adef%20__(epsilon_greedy%2C%20simulate_turns%2C%20uniform_arm)%3A%0A%20%20%20%20_T%20%3D%20200%0A%20%20%20%20simulate_turns(%0A%20%20%20%20%20%20%20%20%5Buniform_arm(10%20*%20i%20%2B%2010)%20for%20i%20in%20range(10)%5D%2C%0A%20%20%20%20%20%20%20%20_T%2C%0A%20%20%20%20%20%20%20%20epsilon_greedy%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20__(idx_maxpayoff%2C%20rd)%3A%0A%20%20%20%20%23%20solu%C3%A7%C3%A3o%0A%20%20%20%20def%20idx_least_chosen(payoff_history)%3A%0A%20%20%20%20%20%20%20%20return%20min(range(len(payoff_history))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20key%3Dlambda%20ix%3A%20len(payoff_history%5Bix%5D))%0A%0A%20%20%20%20def%20epsilon_greedy(narms%2C%20nturns)%3A%0A%20%20%20%20%20%20%20%20def%20choose(payoff_history%2C%20rem_turns)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20there%20are%20other%20ways%20of%20picking%20%CE%B5%E2%82%9C%0A%20%20%20%20%20%20%20%20%20%20%20%20eps_t%20%3D%20rem_turns%20%2F%20nturns%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20rd.random()%20%3C%20eps_t%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20explore%3A%20pick%20least%20tested%20arm%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20idx_least_chosen(payoff_history)%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%20%23%20exploit%3A%20pick%20arm%20with%20greatest%20average%20payoff%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20idx_maxpayoff(payoff_history)%0A%20%20%20%20%20%20%20%20return%20choose%0A%20%20%20%20return%20epsilon_greedy%2C%20idx_least_chosen%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
0b2d5448dddaeb92cbec97f483472c3bf0c6043cd0e062a4de66290ff01eafa0