感想戦 - daruma3940の日記

〜〜〜僕の感想~~~
問題文を読んだ瞬間「どう見ても多腕バンディット問題です。本当にありがとうございました。」だったのでucbとかsoftmaxとかを考えた。
とりあえずnotePlayはせずにucbまたはsoftmaxだけを使ってプレイしてみて探りを入れる。
ばらけさせ方が小さいとあんまりよくないのをひたすら回してしまい、ばらけさせ方が大きくなると一番いいのがわかったぐらいで残り時間が無くなってしまうということが言いたげなデータが得られた（まあそれはそう）。
ここでnotePlayの出番だなということを察する。
最初に何回かnotePlayをすべてのマシンについて回してからucbやsoftmaxを使ってプレイさせてみる。全然よくならない。
パラメータが悪いのだろうか？それともnotePlayによる事前期待値から実際のプレイによる儲けの期待値に移行するのがうまくできてないんだろうか？と考えていろいろやってみる。しかし全然よくならない。
sofxmaxの温度項を多点焼きなましっぽくして探索と活用のバランスを取ろうとしてみる。しかし良くならない。
ucbやsoftmaxに囚われすぎている気がしたので方針を変えてみる。
{全台について何回かnotePlayをした後、一番期待値が高いのを実際にQuickPlayをする}を数回繰り返して、そこから先は一番実際にプレイしたときに出が良かったスロットをひたすら回すことにした。
単純すぎる方法だけどこれが一番スコアが高くなった。（こんなクソ方法に勝てないのは非常にツライ。）
kaggleでちょっとpandas触ったので、pandas使ってデータをプロットして可視化ということをしてみたが
そういうことよりも数個の環境における時系列的な結果をしっかり追って行って何が起こっているのか見たほうがよさそうだったのでデータサイエンティスト気取りはやめた。
時系列データを眺めてみると一番期待値の高いスロットに気が付けているが探索を続けてしまっているということが起こっているので
探索打ち切りの条件を入れてみたが、うまい条件を考えられず結局スコアは落ちる。ここからもいろいろ考えて改良を加えたり、多腕バンディットについてググってやってみるも下がる一方だった。
スコアが下がる一方だったのと手元またはExampleテストではスコアが上がるがフルサブでは下がるというのが繰り返されモチベーションが死んでしまい虚無になった。
きったねぇlogファイルを眺めてても時系列的にどうなってるか理解は深まらずストレスしかたまらん。もっと見やすくためにビジュアライザを作ればよかったという後悔が残るがビジュアライザわからん..みんなやっぱJavaで作ってるんだろうか...

〜〜〜他の人の解法を読んで〜〜〜

作成中

ローカルでの評価，期待値最良台の期待値を e として理論値を coins + max(0, e - 1) * maxTime で計算してそれとの割合を出していた
— ㅤ (@my316g) 2018年3月23日

ローカルでは実際のスコアではなく∑（各スロットの回した回数×真の期待値）、で評価してた。最終サブミットで、上限（期待値最大にquick全ブッパ or なにもせず終了）に対して94%とかだったはず
— yowa (@yowa) 2018年3月23日

ただスコアそのものしか見ていなかった....(´・ω・｀)

やったこと
前半noteplayしてリール期待値出す
後半はUCB方策でquickplay

リール期待値は、焼き鈍し or bitDPでリール復元
noteplay少ないスロットにはリール生成頻度で確率補正
— つっつ (@threepipes_s) 2018年3月23日

リールの予測、とりあえずNotePlayで見たやつを繋げて、最短になるものがベストという焼きなましにしたけど、重複した見えた部分がほんとうに２つあるのか、それとも同じ部分を見たのか、最短が必ずしも正解になるとも限らず、そうなると他のリールの長さもヒントに…とか考えると、めんどい。
— nico_shindannin (@nico_shindannin) 2018年3月23日

もうnote_play()じゃ新情報得られなそうと判断したら不明な部分を最尤で埋め。全マシン50回くらいサンプリングして推定regret出して、noteTimeとのバランス見てquickのみに切り替え
— yowa (@yowa) 2018年3月23日

note_play()して得た情報を最短でつなぎ合わせ（TSPを分枝限定法で）、不明な箇所はランダムな文字で埋めて期待値をサンプリング、最大なマシンをプレイ
— yowa (@yowa) 2018年3月23日

リール期待値、予測の出し方がプロでしょプロ。僕はただnotePlayの結果的に良さそうな感じなのを選んだだけです

あと仮想的にハリボテのスロットマシン（100%の確率で1枚払い戻される）も選択肢に入れた。実マシンが期待値1を下回るものばかりだったらこのハリボテに時間が使われる（実際には時間をたくさん余して終了する形）。期待値1超えるマシンがあるなら、ハリボテに費やした時間を最大なヤツで消費しなおし
— yowa (@yowa) 2018年3月23日

なるほど賢い

まんま Multi-armed Bandit Problem だったので Thompson sampling っぽいことをした
— yowa (@yowa) 2018年3月23日

なんか他にもトンプソンサンプリングしてる人が結構いてるなぁ。
ucbとsoftmaxがうまく行かなかったのでトンプソンもそんなにうまく行かないでしょとおもってしまったのでやらなかったのを後悔

前半は UCB 値使って notePlay、後半は一番良かったやつを quickPlayでした。
後半に移る前には一番良いスロットの wheel 情報で 10 回プレイアウトしてみて、期待値が今のコイン数以下なら後半は端折ります。
— iwashi31 (@iwashi31) 2018年3月23日

そうか前半にucbを使うのかその発想はなかった

UCB で使う各スロットの試行回数は単純に回した回数でなく、今までに得られた wheel 情報を重複排除した後ひとつなぎにして、それら 3 本の長さの積（つまり、取り得る組み合わせ数）の値を使ってみた
— iwashi31 (@iwashi31) 2018年3月23日

ただこれだと 3 本とも以前の情報と重複しちゃったときに UCB 値が変わらず回し続けるみたいなことになるので、別途スロット回した回数も式に加えるみたいな真心をした
— iwashi31 (@iwashi31) 2018年3月23日

なるほどnotePlayで得られた情報量的をこのスロットの試行回数とみなすのか　賢い

おつかれさまでした
noteを13-40回。リールの隣接共通部分を重ねた全長が最小になるよう並び替えの山登り。それで推定したリールからtesterと同様に期待値を計算。一番良かったmachineにquick
— hakomo (@hakomof) 2018年3月23日

・note回数は推定リール長*1.3とした（ある精度を出すために必要なnote回数はリール長に比例するので
・あるmachineの期待値<現ベスト期待値*0.8になったらあるmachineのnoteを枝刈り
・推定リール長の短いものからnoteする（短いほうが期待値が暴れやすく、高めが早く出やすいので枝刈りが加速
— hakomo (@hakomof) 2018年3月23日

・3回山登りして期待値が中央値のリールを推定リールとした（1回山登りや1回焼きなましより良かった）
・左中右のリール長がずれてたら埋めるやつ、generatorの確率で埋めるのとnote結果で埋めるの両方試したけど下がった
— hakomo (@hakomof) 2018年3月23日

他の人もいってるけど推定リールを求めるための焼きなましってどうするんだ...??
notePlayで得られたじょうほうからリールが繋がるように並べ替えるということか？？

wheelの長さは、「本当の長さがLで note_play() をn回すると k種の異なる結果が得られる確率」みたいな式からベイズって、重み付きサンプリング or 最尤推定した。
— yowa (@yowa) 2018年3月23日

観測した文字列をつなぎ合わせる段階では、同じのをまた観測しても無視してた。確率で別箇所としてカウントしたかったけど、つなぎ合わせのTSPがけっこう重い&時間予測できない感じだったので、あんまりつなぎ合わせ処理を呼びたくなかった。
最後に最尤推定するときには出現回数もつかってる
— yowa (@yowa) 2018年3月23日

最初はquick_play()だけで、Thompson samplingしてた。多値だから Beta じゃなく Dirichlet 分布でやってたけど、事前分布はどう定めるのが通例なんだろう。各払い戻しが出る確率に比例した値で、比例定数はテストケースのスロットマシン分布から多数サンプリングして最尤になるように定めたけど
— yowa (@yowa) 2018年3月23日

あくまで Multi-armed Bandit の枠組み（探索と収穫のジレンマ）で考えてたけど、
多くのケースで note_play するのは全体に対して短い期間なんだから、収穫は後の quick_play にまかせて、note_play フェイズでは報酬のことはあまり考えず少ない手数での分布特定に重きを置く方が良かったのかなあ
— yowa (@yowa) 2018年3月23日