報酬の期待値を誤って見積もる2種類の例
「これからの強化学習 2016(編 牧野貴樹)」のp6〜
- 多腕バンディット問題(腕はAとB)を解く例
- 初期の一定試行だけランダムに探索し、その結果から各腕の報酬期待値を計算し、それ以降は最適と推定した選択だけを続ける(greedy)。
- 腕Aの真の報酬確率は0.6
- 腕Bの真の報酬確率は0.4
- 期待値の見積もりを誤る原因は、探索数が少ないこと
1. 腕Bの期待値を高く見積もる誤り
探索中にたまたまBで報酬がたくさん出て、期待値を0.8と見積もった。
その後ずっと、最適であると思われるBを選び続けたが、やがて真の期待値である0.4に近づいていきAよりも期待値が小さいことがわかった。
この場合は、常に期待値を比較して行動を選択していればやがてAを選ぶように修正できる。
2. 腕Aの期待値を低く見積もる誤り
探索中にたまたまAで報酬があまり出ず、期待値を0.2と見積もった。
その後ずっと、最適であると思われるBを選び続けた。
この場合は、常に期待値を比較して行動選択してもAを選ぶことがないのでAの期待値は0.2から更新されず、最適でないBを選び続けることになる。
まとめ
ある時点で探索を打ち切ると、2の例のように本来最適でない行動を選択し続ける可能性がある。
したがって、一定の割合で探索を続けた方が良いのではないか。
→ ε-greedyアルゴリズム
補足
- この問題は教師なし学習では起こりうるが、教師あり学習では起こり得ない。なぜなら、教師あり学習では、あらかじめ訓練データがすべて与えられているから。
- したがって、訓練データが偏る可能性があるタスクに教師あり学習を適用すると同じ問題が発生しうる。
- 理論的には、探索のコストと最適解を取り違えるリスクを統一して扱うためにリグレットに基づく分析が用いられる。