4 ms·
A note on the Thompson sampling: classic TS is optimizing for regret, while the goal here is to identify the 'best arm' (ie. the actual secret value at that pos
by gwern 2y ago
A note on the Thompson sampling: classic TS is optimizing for regret, while the goal here is to identify the 'best arm' (ie. the actual secret value at that position - it's like a 0/1 loss). There is no partial credit in getting part of a password correct, it still won't work. So it's a https://en.wikipedia.org/wiki/Multi-armed_bandit#Best_Arm_Identification https://en.wikipedia.org/wiki/Multi-armed_bandit#Best_Arm_Id...
You can tweak the Thompson sampling to handle best-arm, like https://www.escholar.manchester.ac.uk/api/datastream?publicationPid=uk-ac-man-scw:227658&datastreamId=FULL-TEXT.PDF#pg=140 https://www.escholar.manchester.ac.uk/api/datastream?publica... "Ordered-Statistic Thompson Sampling". I am not sure if the pseudocode TS presented by OP winds up doing the same thing.
- robbieo 2y agoThanks! I believe the actual code is handling this correctly but would love to read that paper – you don't happen to have another link, do you? https://www.escholar.manchester.ac.uk/ https://www.escholar.manchester.ac.uk/ seems to be down for me.
- gwern 2y agoOh, I'm sorry. That should be Mellor 2014, https://pure.manchester.ac.uk/ws/portalfiles/portal/54552919/FULL_TEXT.PDF#page=137 https://pure.manchester.ac.uk/ws/portalfiles/portal/54552919... (If you are curious, I was playing around with best-arm finding algorithms for taste-testing: https://gwern.net/water https://gwern.net/water )