1シンガポール国立大学、量子技術センター、シンガポール
2シンガポール国立大学工学部電気・コンピュータ工学科
この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.
抽象
量子状態の特性のオンライン学習における探査と利用の間のトレードオフの研究を開始します。 未知の量子状態へのシーケンシャル オラクル アクセスが与えられた場合、各ラウンドで、状態に対する期待値 (報酬) を最大化することを目的とした一連のアクションからオブザーバブルを選択するタスクが与えられます。 前のラウンドから得られた未知の状態に関する情報を使用して、アクションの選択を徐々に改善することができます。これにより、報酬と、与えられたアクション セットで達成可能な最大の報酬 (後悔) との間のギャップを減らすことができます。 最適な学習者が被らなければならない累積後悔のさまざまな情報理論的下限を提供し、それが少なくともプレイされたラウンド数の平方根としてスケーリングすることを示します。 また、利用可能なアクションの数と基礎となるスペースの次元に対する累積的な後悔の依存性も調査します。 さらに、有限数の腕と一般的な混合状態の盗賊に最適な戦略を示します。
[埋め込まれたコンテンツ]
►BibTeXデータ
►参照
【1] T. Lattimore と C. Szepesvári。 「盗賊アルゴリズム」。 ケンブリッジ大学出版局。 （2020）。
https：/ / doi.org/ 10.1017 / 9781108571401
【2] A.スリブキンズ。 「多腕盗賊入門」。 機械学習の基礎とトレンド 12, 1–286 (2019).
https：/ / doi.org/ 10.1561 / 2200000068
【3] S. Bubeck と N. Cesa-Bianchi。 「確率的および非確率的多腕バンディット問題の後悔分析」. 機械学習の基礎とトレンド 5、1–122 (2012)。
https：/ / doi.org/ 10.1561 / 2200000024
【4] D. Bouneffouf、I. Rish、および C. Aggarwal。 「多腕およびコンテキストバンディットの適用に関する調査」。 2020 年の IEEE 進化計算会議 (CEC)。 1 ～ 8 ページ。 （2020）。
https:/ / doi.org/ 10.1109/ CEC48606.2020.9185782
【5] L. Tang、R. Rosales、A. Singh、および D. Agarwal。 「コンテキスト バンディットによる広告フォーマットの自動選択」。 情報と知識の管理に関する第 22 回 ACM 国際会議の議事録。 1587 ～ 1594 ページ。 コンピューティング機械協会 (2013)。
https：/ / doi.org/ 10.1145 / 2505515.2514700
【6] M. コーエン、I. ローベル、R. パエス レメ。 「機能ベースの動的価格設定」。 経営科学 66, 4921–4943 (2020).
https：/ / doi.org/ 10.1287 / mnsc.2019.3485
【7] W.トンプソン。 「25つのサンプルの証拠を考慮して、ある未知の確率が別の確率を超える可能性について」. バイオメトリカ 285, 294–1933 (XNUMX).
https:/ / doi.org/ 10.1093/ biomet/ 25.3-4.285
【8] H.ロビンス。 「実験の逐次計画のいくつかの側面」。 アメリカ数学会紀要 58, 527-535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
【9] TL ライと H. ロビンズ。 「漸近的に効率的な適応割り当てルール」。 応用数学の進歩 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
【10] P. Auer、N. Cesa-Bianchi、および P. Fischer。 「多腕バンディット問題の有限時間解析」。 マッハ。 学び。 47、235–256 (2002)。
https：/ / doi.org/ 10.1023 / A：1013689704352
【11] B. カサレ、G. ディ モルフェッタ、H. カドリ、および L. ラライヴォラ。 「量子盗賊」。 量子マッハ。 知性。 2 (2020)。
https://doi.org/10.1007/s42484-020-00024-8
【12] D. Wang、X. You、T. Li、および A. Childs。 「多腕盗賊のための量子探査アルゴリズム」。 人工知能に関するAAAI会議の議事録。 第 35 巻、10102 ～ 10110 ページ。 (2021)。
【13] P. Rebentrost、Y. Hamoudi、M. Ray、X. Wang、S. Yang、および M. Santha。 「ヘッジングとイジング モデルの学習のための量子アルゴリズム」。 物理。 Rev. A 103、012418 (2021)。
https：/ / doi.org/ 10.1103 / PhysRevA.103.012418
【14] O.シャミール。 「バンディット線形最適化の複雑さについて」。 第 28 回学習理論会議の議事録。 Proceedings of Machine Learning Research の第 40 巻、1523 ～ 1551 ページ。 PMLR (2015)。
【15] P. Rusmevichientong と J. Tsitsiklis。 「線形にパラメータ化された盗賊」。 オペレーションズ リサーチの数学 35 (2008)。
https：/ / doi.org/ 10.1287 / moor.1100.0446
【16] J. バリー、DT バリー、および S. アーロンソン。 「量子部分可観測マルコフ決定プロセス」。 物理。 Rev. A 90、032311 (2014)。
https：/ / doi.org/ 10.1103 / PhysRevA.90.032311
【17] M. Ying、Y. Feng、および S. Ying。 「量子マルコフ決定プロセスの最適なポリシー」。 International Journal of Automation and Computing 18, 410–421 (2021).
https：/ / doi.org/ 10.1007 / s11633-021-1278-z
【18] M. パリと J. レハチェク。 「量子状態推定」。 スプリンガー出版社。 （2010）。 第1版。
https：/ / doi.org/ 10.1007 / b98673
【19] S.アーロンソン。 「量子状態のシャドートモグラフィー」。 コンピューティング理論に関する第 50 回 ACM SIGACT シンポジウムの議事録。 325–338ページ。 STOC 2018. コンピューティング機械協会 (2018).
https：/ / doi.org/ 10.1145 / 3188745.3188802
【20] S. アーロンソン、X. チェン、E. ハザン、S. ケール、A. ナヤック。 「量子状態のオンライン学習」。 Journal of Statistical Mechanics: Theory and Experiment 2019 (2018)。
https：/ / doi.org/ 10.1088 / 1742-5468 / ab3988
【21] J. Bretagnolle と C. Huber。 「密度の推定：危険なミニマックス」。 Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 47, 119–137 (1979).
https：/ / doi.org/ 10.1007 / BF00535278
【22] M. Müller-Lennert、F. Dupuis、O. Szehr、S. Fehr、および M. Tomamichel。 「量子Rényiエントロピーについて：新しい一般化といくつかのプロパティ」。 Journal of Mathematical Physics 54、122203 (2013)。
https：/ / doi.org/ 10.1063 / 1.4838856
【23] M. ワイルド、A. ウィンター、D. ヤン。 「サンドウィッチされたRényi相対エントロピーを介したもつれを破るおよびアダマールチャネルの古典的な容量の強力な逆」。 数理物理学におけるコミュニケーション 331, 593–622 (2014).
https：/ / doi.org/ 10.1007 / s00220-014-2122-x
【24] W.ヘフディング。 「有界確率変数の和の確率不等式」。 Journal of the American Statistical Association 58, 13–30 (1963).
https：/ / doi.org/ 10.1080 / 01621459.1963.10500830
【25] P.アウアー。 「搾取と探索のトレードオフに信頼限界を使用する」. Ｊ．マッハ． 学び。 解像度3、397–422（2003）。
https：/ / doi.org/ 10.5555 / 944919.944941
【26] D. Varsha、T. Hayes、および S.Kakade。 「バンディット フィードバック下での確率的線形最適化」. 第 21 回学習理論会議の議事録。 355 ～ 366 ページ。 （2008）。
【27] P. Rusmevichientong と JN Tsitsiklis。 「線形にパラメータ化された盗賊」。 オペレーションズ リサーチの数学 35、395–411 (2010)。
https：/ / doi.org/ 10.1287 / moor.1100.0446
【28] Y. Abbasi-Yadkori、D. Pál、Cs. Szepesvári。 「線形確率的バンディットの改善されたアルゴリズム」。 神経情報処理システムの進歩。 第 24 巻。Curran Associates, Inc. (2011)。
【29] TL ライ。 「適応治療割り当てと多腕バンディット問題」。 統計年報 15, 1091 – 1114 (1987).
https：/ / doi.org/ 10.1214 / aos / 1176350495
【30] M. Guţă、J. Kahn、R. Kueng、JA Tropp。 「最適なエラー境界を備えた高速状態トモグラフィー」。 Journal of Physics A: 数学的および理論的 53、204001 (2020)。
https：/ / doi.org/ 10.1088 / 1751-8121 / ab8111
【31] T.ラティモアとB.ハオ。 「バンディット相回収」。 神経情報処理システムの進歩。 第 34 巻、18801 ～ 18811 ページ。 Curran Associates、Inc.（2021）。
によって引用
[1] Zongqi Wan、Zhijie Zhang、Tongyang Li、Jialin Zhang、Xiaming Sun、「量子多腕バンディットと確率的線形バンディットは対数的後悔を楽しむ」、 arXiv：2205.14988.
[2] Xinyi Chen、Elad Hazan、Tongyang Li、Zhou Lu、Xinzhao Wang、Rui Yang、「量子状態の適応型オンライン学習」、 arXiv：2206.00220.
上記の引用は SAO / NASA ADS （最後に正常に更新された2022-07-24 00:26:50）。 すべての出版社が適切で完全な引用データを提供するわけではないため、リストは不完全な場合があります。
On Crossrefの被引用サービス 作品の引用に関するデータは見つかりませんでした（最後の試行2022-07-24 00:26:48）。
この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。
