1Centro de Tecnologias Quânticas, Universidade Nacional de Cingapura, Cingapura
2Departamento de Engenharia Elétrica e de Computação, Faculdade de Engenharia, Universidade Nacional de Cingapura, Cingapura
Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.
Sumário
Iniciamos o estudo de tradeoffs entre exploração e explotação no aprendizado online de propriedades de estados quânticos. Dado o acesso do oráculo sequencial a um estado quântico desconhecido, em cada rodada, somos encarregados de escolher um observável de um conjunto de ações com o objetivo de maximizar seu valor esperado no estado (a recompensa). As informações obtidas sobre o estado desconhecido das rodadas anteriores podem ser usadas para melhorar gradualmente a escolha da ação, reduzindo assim a lacuna entre a recompensa e a recompensa máxima atingível com o conjunto de ações determinado (o arrependimento). Fornecemos vários limites inferiores da teoria da informação sobre o arrependimento cumulativo que um aluno ideal deve incorrer e mostramos que ele escala pelo menos a raiz quadrada do número de rodadas jogadas. Também investigamos a dependência do arrependimento cumulativo do número de ações disponíveis e da dimensão do espaço subjacente. Além disso, exibimos estratégias que são ótimas para bandidos com um número finito de armas e estados mistos gerais.
[Conteúdo incorporado]
► dados BibTeX
► Referências
[1] T. Lattimore e C. Szepesvári. “Algoritmos de bandidos”. Cambridge University Press. (2020).
https: / / doi.org/ 10.1017 / 9781108571401
[2] A. Slivkins. “Introdução aos bandidos multi-armados”. Fundamentos e tendências em aprendizado de máquina 12, 1–286 (2019).
https: / / doi.org/ 10.1561 / 2200000068
[3] S. Bubeck e N. Cesa-Bianchi. “Análise de arrependimento de problemas de bandidos multi-armados estocásticos e não estocásticos”. Fundamentos e tendências em aprendizado de máquina 5, 1–122 (2012).
https: / / doi.org/ 10.1561 / 2200000024
[4] D. Bouneffouf, I. Rish e C. Aggarwal. “Pesquisa sobre aplicações de bandidos multi-armados e contextuais”. Em 2020 IEEE Congress on Evolutionary Computation (CEC). Páginas 1–8. (2020).
https:///doi.org/10.1109/CEC48606.2020.9185782
[5] L. Tang, R. Rosales, A. Singh e D. Agarwal. “Seleção automática de formato de anúncio por meio de bandidos contextuais”. In Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. Páginas 1587–1594. Association for Computing Machinery (2013).
https: / / doi.org/ 10.1145 / 2505515.2514700
[6] M. Cohen, I. Lobel e R. Paes Leme. “Precificação dinâmica baseada em recursos”. Management Science 66, 4921-4943 (2020).
https: / / doi.org/ 10.1287 / mnsc.2019.3485
[7] W. Thompson. “Sobre a probabilidade de que uma probabilidade desconhecida supere outra em vista da evidência de duas amostras”. Biometrika 25, 285-294 (1933).
https:///doi.org/10.1093/biomet/25.3-4.285
[8] H. Robbins. “Alguns Aspectos do Desenho Sequencial de Experimentos”. Boletim da American Mathematical Society 58, 527-535 (1952).
https://doi.org/10.1090/S0002-9904-1952-09620-8
[9] TL Lai e H. Robbins. “Regras de alocação adaptativas assintoticamente eficientes”. Advances in Applied Mathematics 6, 4-22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8
[10] P. Auer, N. Cesa-Bianchi e P. Fischer. “Análise em tempo finito do problema do bandido multiarmado”. Mach. Aprender. 47, 235-256 (2002).
https: / / doi.org/ 10.1023 / A: 1013689704352
[11] B. Casalé, G. Di Molfetta, H. Kadri, e L. Ralaivola. “bandidos quânticos”. Mach Quântico. Intel. 2 (2020).
https://doi.org/10.1007/s42484-020-00024-8
[12] D. Wang, X. You, T. Li e A. Childs. “Algoritmos de exploração quântica para bandidos multi-armados”. In Proceedings of the AAAI Conference on Artificial Intelligence. Volume 35, páginas 10102–10110. (2021).
[13] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang e M. Santha. “Algoritmos quânticos para hedging e aprendizagem de modelos de ising”. Física Rev. A 103, 012418 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.012418
[14] O. Shamir. “Sobre a complexidade da otimização linear bandida”. In Proceedings of The 28th Conference on Learning Theory. Volume 40 de Proceedings of Machine Learning Research, páginas 1523–1551. PMLR (2015).
[15] P. Rusmevichientong e J. Tsitsiklis. “Bandidos linearmente parametrizados”. Matemática da Pesquisa Operacional 35 (2008).
https: / / doi.org/ 10.1287 / moor.1100.0446
[16] J. Barry, DT Barry e S. Aaronson. “Processos de decisão markov parcialmente observáveis quânticos”. Física Rev. A 90, 032311 (2014).
https: / / doi.org/ 10.1103 / PhysRevA.90.032311
[17] M. Ying, Y. Feng e S. Ying. “Políticas ótimas para processos de decisão de markov quântico”. International Journal of Automation and Computing 18, 410–421 (2021).
https: / / doi.org/ 10.1007 / s11633-021-1278-z
[18] M. Paris e J. Rehacek. “Estimativa de estado quântico”. Springer Publishing Company, Incorporated. (2010). 1ª edição.
https: / / doi.org/ 10.1007 / b98673
[19] S. Aaronson. “Tomografia de sombra de estados quânticos”. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Página 325-338. STOC 2018. Association for Computing Machinery (2018).
https: / / doi.org/ 10.1145 / 3188745.3188802
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale e A. Nayak. “Aprendizagem online de estados quânticos”. Journal of Statistical Mechanics: Theory and Experiment 2019 (2018).
https: / / doi.org/ 10.1088 / 1742-5468 / ab3988
[21] J. Bretagnolle e 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 e M. Tomamichel. “Sobre as entropias quânticas de Rényi: uma nova generalização e algumas propriedades”. Journal of Mathematical Physics 54, 122203 (2013).
https: / / doi.org/ 10.1063 / 1.4838856
[23] M. Wilde, A. Winter e D. Yang. “Converse Forte para a Capacidade Clássica de Quebra de Emaranhamento e Canais Hadamard através de uma Entropia Relativa de Rényi Sanduíche”. Comunicações em Física Matemática 331, 593-622 (2014).
https: / / doi.org/ 10.1007 / s00220-014-2122-x
[24] W. Hoefding. “Desigualdades de probabilidade para somas de variáveis aleatórias limitadas”. Journal of the American Statistical Association 58, 13-30 (1963).
https: / / doi.org/ 10.1080 / 01621459.1963.10500830
[25] P. Auer. “Usando limites de confiança para trade-offs exploração-exploração”. J. Mach. Aprender. Res. 3, 397-422 (2003).
https: / / doi.org/ 10.5555 / 944919.944941
[26] D. Varsha, T. Hayes e S. Kakade. “Otimização linear estocástica sob feedback de bandidos.”. In Proceedings of the 21st Conference on Learning Theory. Páginas 355–366. (2008).
[27] P. Rusmevichientong e JN Tsitsiklis. “Bandidos linearmente parametrizados”. Matemática da Pesquisa Operacional 35, 395–411 (2010).
https: / / doi.org/ 10.1287 / moor.1100.0446
[28] Y. Abbasi-Yadkori, D. Pál e Cs. Szepesvári. “Algoritmos melhorados para bandidos estocásticos lineares”. Em Avanços em Sistemas de Processamento de Informação Neural. Volume 24. Curran Associates, Inc. (2011).
[29] TL Lei. “Alocação de tratamento adaptativo e o problema do bandido multi-armado”. Os Anais de Estatística 15, 1091 – 1114 (1987).
https:///doi.org/10.1214/aos/1176350495
[30] M. Guţă, J. Kahn, R. Kueng e JA Tropp. “Tomografia de estado rápido com limites de erro ótimos”. Revista de Física A: Matemática e Teórica 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111
[31] T. Lattimore e B. Hao. “Recuperação da fase de bandidos”. Em Avanços em Sistemas de Processamento de Informação Neural. Volume 34, páginas 18801–18811. Curran Associates, Inc. (2021).
Citado por
[1] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang e Xiaoming Sun, “Bandidos Multi-Armados Quânticos e Bandidos Lineares Estocásticos Desfrutam de Arrependimentos Logarítmicos”, arXiv: 2205.14988.
[2] Xinyi Chen, Elad Hazan, Tongyang Li, Zhou Lu, Xinzhao Wang e Rui Yang, “Adaptive Online Learning of Quantum States”, arXiv: 2206.00220.
As citações acima são de SAO / NASA ADS (última atualização com êxito 2022-07-24 00:26:50). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.
On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2022-07-24 00:26:48).
Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.
