# Bandit Algorithm (Online Machine Learning)

- Institution: IIT Bombay
- Department: Multidisciplinary
- Teacher: Prof. Manjesh Hanawal
- Level: Graduate
- Language: English
- Subjects: Computer science
- Source: [NPTEL](https://nptel.ac.in/courses/110101145)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/110101145)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

In many scenarios one faces uncertain environments where a-priori the best action to play is unknown. How to obtain best possible reward/utility in such scenarios. One natural way is to first explore the environment and to identify the `best’ actions and exploit them. However, this give raise to an exploration vs exploitation dilemma, where on hand hand we need to do sufficient explorations to identify the best action so that we are confident about its optimality, and on the other hand, best actions need to exploited more number of times to obtain higher reward. In this course we will study many bandit algorithms that balance exploration and exploitation well in various random environment to accumulate good rewards over the duration of play. Bandit algorithms find applications in online advertising, recommendation systems, auctions, routing, e-commerce or in any filed online scenarios where information can be gather in an increment fashion.

INTENDED AUDIENCE : Computer Sceince, Electrical Engineering, Operations Research, Mathematics and Statistics

PREREQUISITES : Basics of Probability Theory and Optimization

## Lectures

1. [Lecture 1 : Introduction to Online Learning –I](https://invisiblenetwork.ai/learn/nptel/110101145/feaa8b5e96d7) (YouTube)
2. [Lecture 2 : Introduction to Online Learning –II](https://invisiblenetwork.ai/learn/nptel/110101145/ac2f576ca6ad) (YouTube)
3. [Lecture 3 : Basics of Statistical Learning](https://invisiblenetwork.ai/learn/nptel/110101145/a7a9abbedfd7) (YouTube)
4. [Lecture 4 : Empirical risk minimization](https://invisiblenetwork.ai/learn/nptel/110101145/339d650e3827) (YouTube)
5. [Lecture 5 : Consistency Halving algorithm](https://invisiblenetwork.ai/learn/nptel/110101145/171b0538f8e5) (YouTube)
6. [Lecture 6 : Online Learnability](https://invisiblenetwork.ai/learn/nptel/110101145/e5c025573132) (YouTube)
7. [Lecture 7 : Standard Optimal Algorithm](https://invisiblenetwork.ai/learn/nptel/110101145/aedec7ee1c0b) (YouTube)
8. [Lecture 8 : Classification in unrealizability case](https://invisiblenetwork.ai/learn/nptel/110101145/fce460bed049) (YouTube)
9. [Lecture 9 : Covers Impossibility Result](https://invisiblenetwork.ai/learn/nptel/110101145/5431ee370287) (YouTube)
10. [Lecture 10 : Weighted Majority](https://invisiblenetwork.ai/learn/nptel/110101145/984fc32f5288) (YouTube)
11. [Lecture 11 : Proof Weighted Majority](https://invisiblenetwork.ai/learn/nptel/110101145/cf2cda1ed36b) (YouTube)
12. [Lecture 12 : Full Information vs Bandit Setting](https://invisiblenetwork.ai/learn/nptel/110101145/2c06a53177ac) (YouTube)
13. [Lecture 13 : Adversarial Bandit Setting](https://invisiblenetwork.ai/learn/nptel/110101145/fbbc9e4d7e04) (YouTube)
14. [Lecture 14 : Exponential Weights for Exploration and Exploitation Algorithm](https://invisiblenetwork.ai/learn/nptel/110101145/6d753be7abbf) (YouTube)
15. [Lecture 15 : Regret Bound of Exp3](https://invisiblenetwork.ai/learn/nptel/110101145/9839dd2640d6) (YouTube)
16. [Lecture 16 : Regret Bound of Exp3(Contd.)](https://invisiblenetwork.ai/learn/nptel/110101145/66d00a8242b3) (YouTube)
17. [Lecture 17 : Exp3.P and Exp3.IX](https://invisiblenetwork.ai/learn/nptel/110101145/ef6df38e356d) (YouTube)
18. [Lecture 18 : Online Convex Optimisation](https://invisiblenetwork.ai/learn/nptel/110101145/ed6455391e0a) (YouTube)
19. [Lecture 19 : Follow the Leader (FTL) Algorithm](https://invisiblenetwork.ai/learn/nptel/110101145/26c7cc9aa8e1) (YouTube)
20. [Lecture 20 : Follow the Regularized Leader](https://invisiblenetwork.ai/learn/nptel/110101145/b7324d48fd18) (YouTube)
21. [Lecture 21 : Online Gradient Descent](https://invisiblenetwork.ai/learn/nptel/110101145/3f4475316e74) (YouTube)
22. [Lecture 22 : Strongly Convex Function](https://invisiblenetwork.ai/learn/nptel/110101145/d33d885eaaf6) (YouTube)
23. [Lecture 23 : FoReL with Strongly Convex Regulariser](https://invisiblenetwork.ai/learn/nptel/110101145/e1be289e2d20) (YouTube)
24. [Lecture 24 : FoReL with Strongly Convex Regulariser (Contd.)](https://invisiblenetwork.ai/learn/nptel/110101145/4c516c47649f) (YouTube)
25. [Lecture 25 : Euclidean and Entropy Regularizer](https://invisiblenetwork.ai/learn/nptel/110101145/f071110aa705) (YouTube)
26. [Lecture 26 : Introduction to Stochastic Bandits](https://invisiblenetwork.ai/learn/nptel/110101145/f402302bfc2e) (YouTube)
27. [Lecture 27 : Concentration Inequalities](https://invisiblenetwork.ai/learn/nptel/110101145/f3d98c6a2ea3) (YouTube)
28. [Lecture 28 : Subgaussian Random Variable](https://invisiblenetwork.ai/learn/nptel/110101145/b6ba489c5708) (YouTube)
29. [Lecture 29 : Regret Definition and Regret Decomposition](https://invisiblenetwork.ai/learn/nptel/110101145/bddef83964b1) (YouTube)
30. [Lecture 30 : Explore and Commit (ETC) Algorithm](https://invisiblenetwork.ai/learn/nptel/110101145/d80b65fc20ac) (YouTube)
31. [Lecture 31 : Regret Analysis and ETC](https://invisiblenetwork.ai/learn/nptel/110101145/a56f50eaa619) (YouTube)
32. [Lecture 32 : Optimism in the Face of Uncertainty](https://invisiblenetwork.ai/learn/nptel/110101145/fcc3ed4538df) (YouTube)
33. [Lecture 33 : Upper Confidence Bound Algorithm](https://invisiblenetwork.ai/learn/nptel/110101145/adbd0ab3acce) (YouTube)
34. [Lecture 34 : Regret Analysis of UCB](https://invisiblenetwork.ai/learn/nptel/110101145/b9e6c737decd) (YouTube)
35. [Lecture 35 : Problem Dependent and Independent Bounds of UCB](https://invisiblenetwork.ai/learn/nptel/110101145/e36b7956d4a4) (YouTube)
36. [Lecture 36 : KL-UCB Algorithm](https://invisiblenetwork.ai/learn/nptel/110101145/e8d9a17091f4) (YouTube)
37. [Lecture 37 : Thompson Sampling - Brief Discussion](https://invisiblenetwork.ai/learn/nptel/110101145/c0bf706e26ca) (YouTube)
38. [Lecture 38 : Proof Idea of Lower Bounds - 1](https://invisiblenetwork.ai/learn/nptel/110101145/5ab89c7e8e7f) (YouTube)
39. [Lecture 39 : Proof Idea of Lower Bounds - 2](https://invisiblenetwork.ai/learn/nptel/110101145/c6591f8a8cc5) (YouTube)
40. [Lecture 40 : Proof of Lower Bound-1](https://invisiblenetwork.ai/learn/nptel/110101145/1a2bdfe3bb0d) (YouTube)
41. [Lecture 41 : Proof of Lower Bound-2](https://invisiblenetwork.ai/learn/nptel/110101145/809bce702117) (YouTube)
42. [Lecture 42 : Stochastic Contextual Bandits](https://invisiblenetwork.ai/learn/nptel/110101145/31c56ebf2939) (YouTube)
43. [Lecture 43 : Introduction to Stochastic Linear Bandits](https://invisiblenetwork.ai/learn/nptel/110101145/82aea555aa9c) (YouTube)
44. [Lecture 44 : Stochastic Linear Bandits](https://invisiblenetwork.ai/learn/nptel/110101145/502bcbb148af) (YouTube)
45. [Lecture 45 : Regret Analysis of SLB-I](https://invisiblenetwork.ai/learn/nptel/110101145/b0c58e9ccd0b) (YouTube)
46. [Lecture 46 : Regret Analysis of SLB - II](https://invisiblenetwork.ai/learn/nptel/110101145/e92750cae4f3) (YouTube)
47. [Lecture 47 : Regret Analysis of SLB-III](https://invisiblenetwork.ai/learn/nptel/110101145/626714c0aa18) (YouTube)
48. [Lecture 48 : Construction of Confidence Ellipsoid - I](https://invisiblenetwork.ai/learn/nptel/110101145/ae33fc2033b4) (YouTube)
49. [Lecture 49 : Construction of Confidence Ellipsoids - II](https://invisiblenetwork.ai/learn/nptel/110101145/f165a315b2fd) (YouTube)
50. [Lecture 50 : Adversarial Contextual Bandits - I](https://invisiblenetwork.ai/learn/nptel/110101145/10d10778f8a9) (YouTube)
51. [Lecture 51 : Adversarial Contextual Bandits II](https://invisiblenetwork.ai/learn/nptel/110101145/37765e80c88a) (YouTube)
52. [Lecture 52 : Exp4 Algorithm](https://invisiblenetwork.ai/learn/nptel/110101145/cb785971394a) (YouTube)
53. [Lecture 53 : Regret of Exp4](https://invisiblenetwork.ai/learn/nptel/110101145/a9f90b889dd4) (YouTube)
54. [Lecture 54 : Adversarial Linear Bandits](https://invisiblenetwork.ai/learn/nptel/110101145/a402c523e376) (YouTube)
55. [Lecture 55 : Exp3 for Adversarial Linear Bandits](https://invisiblenetwork.ai/learn/nptel/110101145/c390f43a0078) (YouTube)
56. [Lecture 56 : Introduction to Pure Exploration and its lower bounds](https://invisiblenetwork.ai/learn/nptel/110101145/d11658991c7a) (YouTube)
57. [Lecture 57 : Uniform Exploration](https://invisiblenetwork.ai/learn/nptel/110101145/6bec6533a914) (YouTube)
58. [Lecture 58 : KL-LUCB](https://invisiblenetwork.ai/learn/nptel/110101145/65010137e089) (YouTube)
59. [Lecture 59 : Lil’ UCB](https://invisiblenetwork.ai/learn/nptel/110101145/11a6da6eb62e) (YouTube)