Introduction_to_Multi Armed_Bandits

Abstract

Multi-armed bandits, a simple but powerful framework for algorithms that make decisions over time under uncertainty. Each chapter tackles a particular line of work conclude with exercises.

Chapter 1-4: The first four chapters are on IID rewards, from the basic model to impossibility results to Bayesian[ˈbeɪziən] priorss to Lipschitz[/ˈlɪpʃɪts/] rewards.

Chapter 5-7: The next three chapters cover adversarial rewards, from the full-feeback version to adversarial bandits to extensions with linear rewards and combinatorially structured actions.

Chapter 8: Chapter 8 is on contextual bandits, a middle ground between IID and adversarial bandits in which the change in reward distributions is completely explained by observable contexts.

Chapter 9-11: The last three chapters cover connections to economic, from learning in repeated games to bandits with supply/budget constraints to exploration in the presence of incentives.

The appendix provides sufficient background on concentration and KL-divergence.

（The chapters on “bandits with similarity information”, “bandits with knapsacks” and “bandits and agents” can also be consumed as standalone surveys on the respective topics.)

序言Preface

• Multi-armed bandits is a multi-disciplinary research area (cs, operations research运筹学, economics and statistics).

• We chose not to dwell on the deep connections to online convex optimization.

• We do not venture into reinforcement learning and subject of several textbooks(something deeper maybe).

• A course based on this book would be complementary to graduate-level courses on online convex optimization and reinforcement learning.

• We do not discuss Markovian models of multi-armed bandits.

Introduction: Scope and Motivation(研究范围和动机)

Outline some of the problems under multi-armed bandits.

Start with three running example, concrete albeit[ɔːlˈbiːɪt] very stytlized[ˈstaɪlaɪzd] (很具体，只是风格被简化了)。

• News website. When a new user arrives, a website site picks an article header to show, observes whether the user clicks on this header. The site’s goal is maximize the total number of clicks.

• Dynamic pricing. A store is selling a digital good, e.g., an app or a song. When a new customer arrives, the store chooses a price offered to this customer. The customer buys (or not) and leaves forever. The store’s goal is to maximize the total profit.

• Investment. Each morning, you choose one stock to invest into, and invest $1. In the end of the day, you observe the change in value for each stock. The goal is to maximize the total wealth.

在基础模型中，一个算法（赌徒）每轮观测到被选的arm(展示的header)带来的reward，但没有其他arms的reward可观测。We have a tradeoff between exploration and exploitation: 基于可获得信息做出最佳近期决策. 算法只想习得最佳动作(arm), 不花费太多时间在探索(exploration)上

class Solution:
    def daysBetweenDates(self, date1: str, date2: str) -> int:
        
        month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]  # 平年的 12 个月的天数
        
        d1, d2 = min(date1, date2), max(date1, date2)  # d1 为较小的日期，d2 为较大的日期
        year1, month1, day1 = (int(i) for i in d1.split('-'))
        year2, month2, day2 = (int(i) for i in d2.split('-'))

        def is_leap(year):
            # 判断是否为闰年
            return year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)
        
        def days_between_two_years(year1, year2):
            # 两个年份之间的间隔天数
            return sum(366 if is_leap(year) else 365 for year in range(year1, year2))
        
        def days_from_year_start(year, month, day):
            # 从当年的1月1号到当天的天数，对于闰年且过了2月的情况，要额外补偿1天
            return sum(month_days[:(month-1)]) + day + (1 if is_leap(year) and month > 2 else 0)

        return  days_between_two_years(year1, year2) + days_from_year_start(year2, month2, day2) - days_from_year_start(year1, month1, day1)