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. "확률적 및 비확률적 multi-armed bandit 문제의 후회 분석". 기계 학습의 기초 및 동향 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. Cohen, I. Lobel 및 R. Paes Leme. "기능 기반 동적 가격 책정". 경영 과학 66, 4921–4943(2020).
https : / /doi.org/ 10.1287 / mnsc.2019.3485
[7] W. 톰슨. "두 샘플의 증거를 고려할 때 하나의 알려지지 않은 확률이 다른 확률을 능가할 가능성". Biometrika 25, 285–294 (1933).
https:/ / doi.org/ 10.1093/ biomet/ 25.3-4.285
[8] H. 로빈스. "순차적 실험 설계의 일부 측면". American Mathematical Society 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. "헤지 및 ising 모델 학습을 위한 양자 알고리즘". 물리학 A 103, 012418(2021).
https : / /doi.org/10.1103/ PhysRevA.103.012418
[14] 오 샤미르. "산적 선형 최적화의 복잡성에 대해". 학습 이론에 관한 28회 회의 진행. 기계 학습 연구 절차 40권, 1523–1551페이지. PMLR(2015).
[15] P. Rusmevichientong 및 J. Tsitsiklis. "선형 매개변수화 도적". 운영 연구의 수학 35(2008).
https : / /doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry 및 S. Aaronson. "양자 부분적으로 관찰 가능한 마르코프 결정 프로세스". 물리학 A 90, 032311(2014).
https : / /doi.org/10.1103/ PhysRevA.90.032311
[17] M. Ying, Y. Feng 및 S. Ying. "퀀텀 마르코프 결정 프로세스를 위한 최적의 정책". 국제 자동화 및 컴퓨팅 저널 18, 410–421(2021).
https : / /doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris 및 J. Rehacek. "양자 상태 추정". Springer 출판 회사, Incorporated. (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. Aaronson, X. Chen, E. Hazan, S. Kale 및 A. Nayak. "양자 상태의 온라인 학습". 통계 역학 저널: 이론 및 실험 2019 (2018).
https : / /doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle 및 C. Huber. "Estimation des densités: risque minimax". 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. "양자 렌이 엔트로피: 새로운 일반화 및 일부 속성". 수리 물리학 저널 54, 122203 (2013).
https : / /doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter 및 D. Yang. "Sandwiched Rényi Relative Entropy를 통한 Entanglement-Breaking 및 Hadamard 채널의 고전적 용량에 대한 강력한 대화". 수학 물리학 331, 593–622(2014)의 커뮤니케이션.
https : / /doi.org/ 10.1007 / s00220-014-2122-x
[24] W. 호프딩. "제한된 무작위 변수의 합에 대한 확률 불평등". 미국 통계 협회 저널 58, 13–30(1963).
https : / /doi.org/ 10.1080 / 01621459.1963.10500830
[25] P.Auer. "착취-탐색 절충을 위한 신뢰 범위 사용". J. 마하. 배우다. 해상도 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. Lattimore 및 B. Hao. "산적 단계 검색". 신경 정보 처리 시스템의 발전. 34권, 18801–18811페이지. Curran Associates, Inc.(2021).
인용
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang 및 Xiaoming Sun, "Quantum Multi-Armed Bandits 및 Stochastic Linear Bandits Enjoy Logarithmic Regrets", 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).
이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.
