【dqn】初恋はあきらめろ？？

前回取り上げた秘書問題を再度取り上げようと思います。

秘書問題の大きな課題として以下二つの問題があります
１．応募者１００人を超えてどこまで学習できるのか
２．理論はnが大きいとして$e/n$を導いているが、$n$が小さいときはどうなるの？？
恋するウワンとしては、２の課題の方が切実なので今回はこれを取り上げてみたいと思います。

２．理論はnが大きいとしてe/nを導いているが、nが小さいときはどうなるの？？

まず、採用成功率の推移を見てみましょう。

n=50
Episode 1: reward: 0.000, steps: 27
採用成功率(1000回)：0.394
n=20
Episode 1: reward: 0.000, steps: 20
採用成功率(1000回)：0.396
n=10
Episode 1: reward: 0.000, steps: 6
採用成功率(1000回)：0.401
n=8
8人中2人目（暫定順位：1位）
8人中3人目（暫定順位：3位）
8人中4人目（暫定順位：1位）
おめでとうございます！  最良の応募者を採用できました。
Episode 1: reward: 1000.000, steps: 4
採用成功率(1000回)：0.429
5人中2人目（暫定順位：2位）
5人中3人目（暫定順位：3位）
5人中4人目（暫定順位：3位）
5人中5人目（暫定順位：1位）
おめでとうございます！  最良の応募者を採用できました。
Episode 1: reward: 1000.000, steps: 5
採用成功率(1000回)：0.43
n=3
3人中2人目（暫定順位：2位）
3人中3人目（暫定順位：1位）
おめでとうございます！  最良の応募者を採用できました。
Episode 1: reward: 1000.000, steps: 3
採用成功率(1000回)：0.527
n=2
おめでとうございます！  最良の応募者を採用できました。
Episode 1: reward: 1000.000, steps: 1
採用成功率(1000回)：0.516

表にすると以下のとおりです。

応募者数	2	3	5	8	10	20	50	$\infty$
採用成功率	0.516	0.527	0.43	0.429	0.401	0.396	0.394	0.3678

これをグラフにすると以下のとおりです。

ちょっと考察すると、つまり応募者無限大だと0.3678に収束し、2人の時は乱数に偏りなく選べば0.5になるだろう。その間は滑らかに連結されているだろう。というわけで、今回の採用成功率はそれほど間違ってもいないようだ。

以下採用状況の全体図を並べてみる。






並べてみると、すべてのパターンが似ているのが分かります。
つまり、応募者数が大きいときは肌理が細かくなりますが、おおまかな傾向という意味ではよく似ています。
戦略の変更点については、以下のとおりになっています。
戦略の変更点は$n/e$のポイントよりn=50を除いて、全体に少し大きめになっているのが分かります。

つまり、ここで重要なことは、すべての領域で最初の面接者はスルーしろという結論だということです。
そして、応募者が増えれば増えるほど、スルーした方がより優秀な人を採用できる可能性があって、その戦略の転換点が$n/e$だという点だということです。
もちろん、このお話は応募者を序列化できるという前提での話だし、状況もそれぞれ変化するので、初恋に適用できる話ではありません。

まとめ

・応募者数を変化させて応募者が少ないときもDQNで得られる戦略が妥当なことを見た
・その結果、応募者が少ない領域でも最初の人はあきらめろという戦略が導かれる

・解析的に解く場合に比較すると、DQNは全体に精度がいまいちな気がする