マルコフ性文脈線形バンドに対するリダクションアルゴリズム

概要: 最近の研究では、文脈が i.i.d. に抽出される場合、線形文脈バンディットは単一文脈線形バンディットへ還元できることが示されている。この「文脈は安価である」という視点は非常に有利であり、有限時間解析をより鋭く行えるとともに、誤指定や敵対的汚染に関する線形バンディット研究の成熟した手法を活用できる。時間的に相関した可用性を持つ応用に動機づけられ、我々はこの視点を外因性のマルコフ連鎖によって行動集合が進化するマルコフ過程の文脈線形バンディットへ拡張します。私たちの主な貢献は、一様幾何遍歴性の下で適用される還元です。標準的な線形バンディットオラクルを用いて問題を解くための定常な代理行動集合を構築し、非定常な条件付き文脈分布によって生じるバイアスを制御する遅延更新スキームを採用します。さらに、未知の遷移分布のための段階的アルゴリズムをオンラインで代理写像を学習することを提供します。いずれの設定においても、基礎となる線形バンディットオラクルと一致する高確率の最悪ケース後悔境界を得ることができ、混合時間に関しては低次の依存性のみを持ちます。