講演抄録/キーワード |
講演名 |
2015-06-23 15:45
HedgeとExp3アルゴリズム間の橋渡し ○中村篤祥(北大) IBISML2015-13 |
抄録 |
(和) |
Hedgeアルゴリズムは,それまでのパフォーマンスに基づく確率分布に従ってエキスパートを選択するオンライン学習アルゴリズムである.Hedgeは選択したエキスパートのみでなく,すべてのエキスパートの利得を毎回知ることができるフルインフォメーション設定において動作するように設計されているが,選択したエキスパートの利得のみ知ることができるバンディット設定において動作するように改造された版はExp3アルゴリズムとして知られている.本稿では,これら2つの設定をパラメータ${gamma_i}$で結ぶ新しいモデルを考え,2つのアルゴリズムの拡張であるHExp3アルゴリズムを提案し,擬似リグレットの上界と下界を証明する. |
(英) |
Hedge is an online learning algorithm that draws an expert according to a probability distribution which depends on the performance of each expert so far. Hedge works for the {em full-information} setting, in which the rewards of all the experts are revealed. Exp3 is a Hedge-based algorithm modified so as to work for {em bandit} setting, in which only the reward of the selected
expert is revealed. In this paper, we consider a new model with parameters ${gamma_i}$ that connect the two settings, and propose HExp3 algorithm that is an extension of both the two algorithms. We show upper and lower bounds of pseudo regret of HExp3. |
キーワード |
(和) |
オンライン学習 / バンディット / リグレット分析 / / / / / |
(英) |
online learning / bandit / regret analysis / / / / / |
文献情報 |
信学技報, vol. 115, no. 112, IBISML2015-13, pp. 81-86, 2015年6月. |
資料番号 |
IBISML2015-13 |
発行日 |
2015-06-16 (IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IBISML2015-13 |