Multi-Armed Bandits in Active Learning
Mojmir Vinkler

21. 11. 2013

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

1 / 12

Multi-armed bandit problem

Originally considered by Allied scientists in World War II, it proved so intractable that, according to Peter Whittle, it was proposed the problem be dropped over Germany so that German scientists could also waste their time on it.

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

2 / 12

Multi-armed bandit problem
Problem statement
Gambler faces m slot machines with hidden probabilities of winning µ1 , . . . , µm . Each turn he must decide which arm to pull. His aim is to maximize sum of rewards T rt or alternatively minimize total regret to t=1 always pulling the most profitable arm
T

ρ = T max µk − k t=1

rt

His strategy is called zero-regret if 1 ρ=0 T →∞ T lim

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

3 / 12

Exploration vs Exploitation

Exploration = search for more profitable arms X Exploitation = collect reward from the most profitable arm

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

4 / 12

Strategies
Epsilon-greedy strategy The best lever is selected for a proportion 1 − of the trials, and another lever is randomly selected (with uniform probability) for a proportion . Epsilon-first strategy A pure exploration phase is followed by a pure exploitation phase. For T trials in total, the exploration phase occupies T trials and the exploitation phase (1 − )T trials. Epsilon-decreasing strategy Similar to the epsilon-greedy strategy, except that the value of decreases as the experiment progresses, resulting in highly explorative behaviour at the start and highly exploitative behaviour at the finish. ...

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

5 / 12

Probabilistic (bayesian) approach

Probability of pulling an arm should match its actual probability of having highest reward.

Math intermezzo
Let ai be number of wins and bi number of losses from pulling arm i up to time t. Posterior distribution of random variable µi is then µi ∼ Beta(ai + 1, bi + 1) and we should play arm i with probability P(pull i-th arm) = P(µi = max{µk }) k Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

6 / 12

Interactive Demo
Mojmir Vinkler () Multi-Armed Bandits in Active Learning 21. 11. 2013 7 / 12

Applications

Gambling? Online advertising Which ad should we display to maximize our revenues? Google uses that for ranking. Clinical trials Choose treatment to minimize patient losses. Adaptive routing Minimize delays in a network. Project management Split budget into projects based on their revenues. Active learning. . .

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

8 / 12

Active learning
Problem statement
Let P = {x1 , . . . , xn } be a pool of unlabeled points sampled i.i.d from PX and O a labeling Oracle. We can query Oracle for x and get its label y ∼ PY |X =x . Our aim is to find hypothesis h ∈ H minimizing loss function R(h) = Ex,y ∼P L(h(x), y ) using as little data as possible. In our case hypothesis ∼ model parameters and L(h(x), y ) = L(yh(x)) since y ∈ {−1, 1}.

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

9 / 12

MAB in Active Learning

Bandit arms ←→ Hypotheses from H Pulling arm ←→ Testing hypothesis h Reward ←→ ?

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

10 / 12

Algorithm
Inputs: {xi }, H, loss function L(·)
1

Choose hypothesis (pull an arm) Pick ht+1 using any of the MAB methods, in the study they use lower confidence bound ht+1 = arg min LCBt (h) h∈H 2

Estimate all labels yi = yi if we know label of xi sign(ht (xi )) otherwise

3

Query for label of xi Query for point xi with probability proportional to how badly classified it is (in terms of loss function) pit ∝ L(y i ht (xi ))

4

Repeat
Mojmir Vinkler () Multi-Armed Bandits in Active Learning 21. 11. 2013 11 / 12

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

12 / 12

References

Ravi Ganti and Alexander G. Gray Building Bridges: Viewing Active Learning from the Multi-Armed Bandit Lens Conference on Uncertainty in Artificial Intelligence, July 11-15, 2013.

Mojmir Vinkler ()

Multi-Armed Bandits in Active Learning

21. 11. 2013

13 / 12