文献

J-GLOBAL ID：201702287663954267   整理番号：17A0869727

敵対的組合せバンディット問題に対するZDDを用いたアルゴリズム

Efficient Adversarial Combinatorial Bandit Algorithm via Zero-suppressed Decision Diagrams

著者 (3件)： 坂上晋作 (NTT コミュニケーション科学基礎研) ,  石畠正和 (北大 大学院情報科学研究科) ,  湊真一 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 110(IBISML2017 1-10)  ページ： 43-48  発行年： 2017年06月16日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究では,敵対的組合せバンディット問題に対するアルゴリズムを提案する。この問題は,各時刻における行動を逐次的に選択する問題であり,提案法は経過時間に対して劣線形なリグレットを常に達成する。また,提案法の手続きはゼロサプレス型二分決定グラフ(ZDD)を用いて計算可能なため,選択可能な行動の総数が指数的に増加する場合であっても,各時刻での行動を効率的に計算することができる。(著者抄録)

シソーラス用語： 最適化問題 ,  *アルゴリズム ,  *二分決定グラフ ,  選択 ,  標本抽出 ,  実験 ,  *強化学習
準シソーラス用語： サンプリング【統計】 ,  ゼロサプレス型二分決定 ,  バンディット問題 ,  共起確率 ,  数値実験 ,  選択肢

分類 (1件)： 人工知能  (JE08000Z)

引用文献 (23件)：

• H. Robbins, ”Some aspects of the sequential design of experiments,” Herbert Robbins Selected Papers, pp.169-177, Springer, 1985.
• V. Kuleshov and D. Precup, ”Algorithms for multi-armed bandit problems,” arXiv preprint arXiv:1402.6028, pp. ? ? -? ? , 2014.
• L. Li, W. Chu, J. Langford, and R.E. Schapire, ”A contextual-bandit approach to personalized news article recommendation,” 19th international conference on World wide webACM, pp.661-670 2010.
• B. Awerbuch and R.D. Kleinberg, ”Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches,” 36th Annual ACM Symposium on Theory of Computing, pp.45-53, ACM, 2004.
• A. Gy?rgy, T. Linder, G. Lugosi, and G. Ottucs?k, ”The on-line shortest path problem under partial monitoring,” J. Mach. Learn. Res., vol.8, no.Oct, pp.2369-2403, 2007.

タイトルに関連する用語 (4件)： 敵対 ,  組合せ ,  ZDD ,  アルゴリズム