Efficient Algorithms for Online Decision Problems

Explore efficient algorithms for online decision problems, expert selection, and minimizing regret in decision-making. Covering topics such as linear generalization, predicting from expert advice, and notable notations used in optimization. Dive into strategies for decision-making without prior knowledge of future outcomes.

• Algorithms
• Decision Problems
• Expert Advice
• Regret Minimization
• Optimization

sday Follow

Uploaded on Mar 05, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Efficient algorithms for online decinsion problems Adam Kalai, Santosh Vempala Seminar on Experts and Bandits, Fall 17/18 Ran Hochshtet

2. Contents Online decision problem N Experts Online shortest paths Tree update problem ??? ? ??? ? ??? ? 2

3. Introduction Online decision problem No knowledge of the future Each period we pick choice Pay ???? 0,1 Goal: Minimize the regret 3

4. Linear generalization Series of decisions ?1,?2 from infinite set ? ? ??leads to state ?? ? ? Making decision ? in state ? costs ? ? Total cost = ?=1 ?? ?? ? 4

5. Linear generalization ? ? ?- state ? ? ?- decision ? ? = arg???? ?? ? M computes the best single decision in hindsight ??? ?????= min ? ?1+ + ?? ?1+ + ?? ? ? ? ? ?=1 ? ?? ?=1 ? ??= min ??= 5

6. Predicting from expert advice ? experts Each period we pick expert Pay ???? 0,1 Goal: Minimize the regret 6

7. Predicting from expert advice ? experts problem ??- the costs vector ??= ?1,?2, ,?? ??= 1,?????? ?????? ? 0,?? ?????? 7

8. Motivation Consider example with two experts The costs are: Expert 1 0 1 0 1 0 Expert 2 1/2 0 1 0 1 Follow the leader always incurs cost of 1 The total cost is ? Using perturbations we can achieve ? 2 8

9. ??? ? On each period t: Choose ??uniformly at random from the cube 0,1 ? Use ? ?1+ + ?? 1+ ?? ? 9

10. ???? On each period t: Choose ??at random according to the exponential distribution ?? ?? Use ? ?1+ + ?? 1+ ?? 10

11. Notations for ? ? for all ?,? ? for all ? ?,? ? for all ? ? ? ? ? ? ? |? ?| ? ?1 ?1= ?=1 ?? 1 11

12. Theorem 1.1 Let ?1,?2, ,?? ? be a state sequence (a) Running ??? with ? 1 gives: ? ???? ?? ??? ? ??? ?????+ ???? +? ? 12

13. Theorem 1.1 Let ?1,?2, ,?? ? be a state sequence (b) For nonnegative ?,? ?+ ?, ??? gives: ? ? ???? ?? ??? 2? 1 + ? ??? ?????+4?? 1 + ln? ? 13

14. Theorem 1.1 If ? or ??? ?????are known: For FPL: ??? ?????+ ???? +? ? ???? ?? ??? ? ? ? ???? ?? ??? ?/??? ??? ?????+ 2 ???? 14

15. ? Experts problem ? ? ? ? ?1 It seems that ? = 2, ? = ? In our algorithm the worst case is when each period only one expert incurs cost 1 ? ? ? ? 0 0 0 ? 0 0 0 ? , , Min-cost is b After we choose b, there is a chance we choose c 15

16. ? Experts problem ? ? ? ? ?1 ? = 2, ? = 1 By Theorem 1.1 (b): 1 ? 1 + ? ??? ?????+4?? 1 + ln? ? ???? ?? ??? ? ???? ?? ??? ? 2? ? 2 log? ? 1 + ? ??? ?????+ ? 16

17. Online shortest paths Input Directed Graph - ? = ?,? Pair of nodes ?,? Each period pick path from ? to ? Then times on all edges are revealed The cost is the sum of times on the chosen path 17

18. Online shortest paths ? is the number of edges ??- the times vector ??= ?1,?2, ,?? ??= 1,? ???? ???? ? 0,?? ?????? 18

19. Online shortest paths Use ??? On each period ? = 1,2,3, For each edge ? pick ??? from exp. Distribution (same as ??? ) ??? = the total times on edge ? so far Use shortest path in the graph with weights ??? + ??? 19

20. Online shortest paths ? ? ? ? ?1 ? = ?, ? = ? By Theorem 1.1: 1 ? 1 + ? ??? ?????+4?? 1 + ln? ? ???? ?? ??? 2? ? ?? log? ? ? ???? 1 + ? ??? ?????+ ? 20

21. Proof of Theorem ?.? - ??? ?1:?= ?1+ ?2+ + ?? Be the leader use ? ?1:? instead of ? ?1:? 1 Be the leader has no regret Prove by induction 21

22. Proof of Theorem ?.? - ??? We show that: ?=1 For ? = 1 trivial Induction step from ? to ? + 1: ? ? ?1:? ?? ? ?1:? ?1:? ?+1 ? ? ?1:? ??= ? ?1:? ??+ ? ?1:?+1 ??+1 ?=1 ? ?1:? ?1:?+ ? ?1:?+1 ??+1 ? ?1:?+1 ?1:?+ ? ?1:?+1 ??+1= ? ?1:?+1 ?1:?+1 ?=1 22

23. Lemma ?.? We want to show that perturbations do not hurt too much Still be the leader algorithm For any state sequence ?1,?2, , any ? > 0 and any vectors ?0= 0,?1,?2, ,?? ? ? ? ? ?1:?+ ?? ?? ? ?1:? ?1:?+ ? ?? ?? 1 ?=1 ?=1 23

24. ? ? ?1:? ?? ? ?1:? ?1:? Proof of Lemma ?.? ?=1 ? ? ? ? ? ? ? ??= ?? ?? 1 Pretend ??= ??+ ?? ?? 1 ?1+ ?1 ?0+ + ??+ ?? ?? 1= ?1:?+ ?? ?=1 ? ?1:?+ ?? ??+ ?? ?? 1 ? ?1:?+ ?? ?1:?+ ?? ? ?1:? ?1:?+ ?? = ? ?1:? ?1:?+ ? ?1:? ??= ?=1 ? ? ? ?1:? ?1:?+ ? ?1:? ?? ?? 1 ?=1 24

25. ? ? ?1? ? ? ? 1 Proof of Lemma ?.? ? ? ?=1 ? ?1:?+ ?? ??+ ?? ?? 1 ? ?1:? ?1:?+ ?=1 ? ?1:? ?? ?? 1 ? ? ?=1 ? ?1:? ?1:?+ ?=1 ? ?1:?+ ?? ?? ? ?1:? ?1:?+ ?=1 ? ? ?1:? ? ?1:?+ ?? ? ?1:? ? ?1:?+ ?? 1 ?? ?? 1 ?? ?? 1 ? ? ?1:? ?1:?+ ? ?? ?? 1 ?=1 25

26. ? ? ? ?1:?+ ?? ?? ? ?1:? ?1:?+ ? ?? ?? 1 Proof of Theorem ?.? - ??? ?=1 ?=1 Use ??= ?1, for all ? > 1 No need to choose new ??each period Applying Lemma 3.1: ? ? ??+ ?1 ?? ? ?1:? ?1:?+ ? ?1 ?=1 ? ?1:? ?1:? +? ? 26

27. ??? ?????+ ???? +? ? ???? ?? ??? ? ? Proof of Theorem ?.? - ??? ? ? ??+ ?1 ?? ? ?1:? ?1:? +? ? ?=1 Now we return to use ? ?1:? 1+ ?? instead of ? ?1:?+ ?? We need to show that: ? ? ?1:? 1+ ?1 ?? ? ? ?1:?+ ?1 ?? + ??? 27

28. ? |? ?| Proof of Theorem ?.? - ??? Key idea: the distributions over ?1:? 1+ ??and ?1:?+ ??are similar If the cubes are identical, i.e. ?1:? 1= ?1:?, then ? ? ?1:? 1+ ?? ?? = ? ? ?1:?+ ?? ?? If they overlap on fraction ? of their volume: ? ? ?1:? 1+ ?? ?? ? ? ?1:?+ ?? ?? + 1 ? ? 28

29. Lemma ?.? ? ? For any ? ?, the cubes 0,1 least a 1 ? ?1 fraction and ? + 0,1 overlap in at ? ? 29

30. Proof of Lemma ?.? ?, Take a random point ? 0,1 ? ?, then for some ?, ?? ??+ 0,1 ? if ? ? + 0,1 ? ? ? ? ?? ??+ 0,1 ?? 1 ? = ? ?? ? With union bound we get: ? ? ?? ? ? ? ? ? + 0,1 1 ? ?1 ? 30

31. ? ?1 ??? ?????+ ???? +? Proof of Theorem ?.? - ??? ? ???? ?? ??? ? ? By lemma 3.2: 1 ? ? ?? 1 ?? Each period the difference between using ?1:? 1+ ?? and ?1:?+ ??is at most ??? We get: ??? ?????+ ???? +? ? ???? ?? ??? ? ? 31

32. The tree update problem Maintain a binary search tree over ? items There is an unknown sequence of accesses The cost is the number of comparisons Equals to the depth in the tree 32

33. The tree update problem We can solve the problem with ??? Each period we find the best tree so far, and use it The problem: For each access we do expensive computation 33

34. The tree update problem Follow the lazy leading tree ? : For 1 ? ?, let ?? 0 and choose ??randomly from 1,2, ,? Start with best tree as if there were ??accesses to node ? After each access to item ?: (a) ?? ??+ 1 (b) if ?? ??then i. ?? ??+ ? ii. Compute best tree as if there were ??accesses to node ? 34

35. ??? ? Calling the oracle can be a computationally expensive We want to minimize the numbers of times we use ? Trick: use ?1:? 1+ ??= ?1:?+ ??+1as often as possible 35

36. ??? ? ??? is equivalent to ??? in terms of expected cost ??? rarely calls the oracle ??? rarely changes decision from one period to the next 36

37. ??? ? ? Once, choose ? 0,1 uniformly ? Determine a grid: ? = ? +1 On period ?. Use ? ?? 1 where ?? 1is the unique point in ? ?1:? 1+ 0,1 If ?? 1= ??- no need to re-evaluate ? ?? ?? ? ? ? ? 37

38. ??? ? 38

39. Lemma ?.? For any fixed sequence of states ?1,?2, ??? ? and ??? ? (also ??? ? and ??? ? ) have identical expectations on each period ?. The probability of ??? ? (or ??? ? ) performing an update is at most ??. 39

40. Proof of Lemma ?.? ??? ? chooses a uniformly random grid of spacing 1 /? ? There is exactly one grid point inside ?? 1+ 0,1 By symmetry ?? 1is uniformly distributed over ? ? ?? 1+ 0,1 ? ? Same as ??? ? - uniform over ?1:? 1+ 0,1 ? 40

41. Lemma 3.2: For any ? ?, the cubes 0,1 overlap in at least a 1 ? ?1 fraction ? ? and ? + 0,1 Proof of Lemma ?.? ? ? ? ?1 In each update: ?? 1 ?? The grid point of ?1:? 1+ 0,1 ? is not in the cube ? ? ?1:?+ 0,1 By lemma 3.2: Pr ?????? ? ?? 1 ?? ? 41

42. Summary Online decision problem N Experts Online shortest paths Tree update problem ??? ? ??? ? ??? ? 42

43. THANKS! ANY QUESTIONS? 43