Implement (environment and) algorithm(s) from "Adaptively Tracking the Best Arm with an Unknown Number of Distribution Changes"

[Naereen]

This recent article ["Adaptively Tracking the Best Arm with an Unknown Number of Distribution Changes". Peter Auer, Pratik Gajane and Ronald Ortner] is really interesting. They quote our work on doubling-trick, but I'm mostly interested about the piecewise stationary bandit model they study.

• I should read it more carefully,
• I need to implement more "dynamic" scenarios in SMPyBandits, see Implement more "dynamic" scenarios #71, and the other issues Implement EXP3.R to tackle switching bandits ? #100, Implement Memory Bandits for switching bandits #130,
• And implement in SMPyBandits their algorithm(s),
• To do my own comparison against other "switching algorithms", mainly the naive sliding-window UCB and discounted UCB (from ["On upper-confidence bound policies for non-stationary bandit problems", Aurélien Garivier, Eric Moulines, arXiv 0805.3415]),
• And check and verify their claims. (or disprove them?)
• Also check that their algorithm can be adapted to work without knowing horizon T by using my DoublingTrickWrapper algorithm.

[Naereen]

It's a really complicated algorithm…

[Naereen]

http://banditslilian.gforge.inria.fr/docs/Policies.AdSwitch.html

[Naereen]

Example of regret for stationary bandit (K=9 arms, µ=[0.1,…,0.9]), T=1000 and N=10 repetitions (basic simulation):

• Final regret of different policies:
  
• Evolution of regret:
  

Example of regret for piecewise stationary bandit (K=2 arms, T=10000, N=16 repetitions):

• Problem (history of means of arms)
  
• Evolution of regret:
  
• AdSwitch seems to be not too costly in comparison with other policies:
  

[Naereen]

With this implementation, I'm sure my DoublingTrickWrapper can be used with AdSwitch. I'm not even going to try, because I don't have time to check if my implementation is correct or explore why AdSwitch seems to be inefficient!

[Naereen]

They improved their paper, it was published in COLT 2019, see here in PLMR, volume 99.

[haoyuzhao123]

I am not surprised to see that the inefficiency of AdSwitch in your experiments. Their main contribution is theoretically showing that AdSwitch is optimal and parameter free. In your experiment, the regret curve is almost straight in each section, and I guess that the time horizon in each section is not enough. I guess that in each section, the time should satisify T = 10,0000 and maybe you can observe the sqrt(t) curve.

[Naereen]

Hi @haoyuzhao123,
Thanks for your remark, you are right.
Regards.

[Naereen]

I have to implement the newest version, which seems simpler to code.

[Naereen]

I guess I'm done? I'm trying on a few experiments… I hope the code is not too bugged!

[Naereen]

I guess the code works, but it's EXTREMELY slow. I have to try to implement their suggestion for speeding up the for loops:

[Naereen]

I think I'm done for this… I should work more, but I don't know what to do:

• I don't understand their idea of optimization, it cannot reduce the complexity from $O(K t^3)$ to $O(K (\log(T))^2)$, this just seems impossible to me. I get the idea, but don't really know how to implement it!
• I did some test where the AdSwitch algorithm performs much more efficient than stupid algorithms (e.g., uniform $U({1,\dots,K})$), and similarly to algorithms non-aware of the non-stationarity, and almost as well as OracleRestart.
• 💥 but the algorithm is extremely slow to run, for instance for N=16 repetitions and T=1000 it takes 12 seconds, so for just T=1500 (simply 1.5 more, so a complexity in $O(T^4)$ should multiply by $1.5^4 \simeq 5$), it indeed takes up-to 72 seconds, that's just normal. But it's way too slow!

[Naereen]

Some results of (tiny horizon) numerical simulations

Problem 1 (T=2000 and N=128 rep)

Problem 2 (T=2000 and N=128 rep)

Problem 3 (T=2000 and N=128 rep)

(problem 4 in our paper)

Problem 4 (T=2000 and N=128 rep)

(not in our paper)