* Ortutay (2021) Barbara Ortutay. 2021\.  What’s in a tag? Twitter revamps misinformation labels.  https://apnews.com/article/health-coronavirus-pandemic-election-2020-misinformation-technology-37cee761758f1072f91e1a362f769f5e.
  * Ozturk et al. (2015) Pinar Ozturk, Huaye Li, and Yasuaki Sakamoto. 2015.  Combating rumor spread on social media: The effectiveness of refutation and warning. In _2015 48th Hawaii international conference on system sciences_. IEEE, 2406–2414.
  * Pan et al. (2022) Christina A. Pan, Sahil Yakhmi, Tara P. Iyer, Evan Strasnick, Amy X. Zhang, and Michael S. Bernstein. 2022.  Comparing the Perceived Legitimacy of Content Moderation Processes: Contractors, Algorithms, Expert Panels, and Digital Juries.  _Proc. ACM Hum.-Comput. Interact._ 6, CSCW1, Article 82 (apr 2022), 31 pages.  https://doi.org/10.1145/3512929
  * Pan et al. (2012) Xunyu Pan, Xing Zhang, and Siwei Lyu. 2012.  Exposing image splicing with inconsistent local noise variances. In _2012 IEEE International conference on computational photography (ICCP)_. IEEE, 1–10.
  * Pennycook et al. (2020a) Gordon Pennycook, Adam Bear, Evan T Collins, and David G Rand. 2020a.  The implied truth effect: Attaching warnings to a subset of fake news headlines increases perceived accuracy of headlines without warnings.  _Management Science_ 66, 11 (2020), 4944–4957.
  * Pennycook et al. (2018) Gordon Pennycook, Tyrone D Cannon, and David G Rand. 2018\.  Prior exposure increases perceived accuracy of fake news.  _Journal of experimental psychology: general_ 147, 12 (2018), 1865\.
  * Pennycook et al. (2020b) Gordon Pennycook, Jonathon McPhetres, Yunhao Zhang, Jackson G Lu, and David G Rand. 2020b.  Fighting COVID-19 misinformation on social media: Experimental evidence for a scalable accuracy-nudge intervention.  _Psychological science_ 31, 7 (2020), 770–780.
  * Pennycook and Rand (2017) Gordon Pennycook and David G Rand. 2017.  Who falls for fake news? The roles of analytic thinking, motivated reasoning, political ideology, and bullshit receptivity.  _SSRN Electronic Journal_ 88, 2 (2017), 1–63.
  * Pennycook and Rand (2019a) Gordon Pennycook and David G Rand. 2019a.  Fighting misinformation on social media using crowdsourced judgments of news source quality.  _Proceedings of the National Academy of Sciences_ 116, 7 (2019), 2521–2526.
  * Pennycook and Rand (2019b) Gordon Pennycook and David G Rand. 2019b.  Lazy, not biased: Susceptibility to partisan fake news is better explained by lack of reasoning than by motivated reasoning.  _Cognition_ 188 (2019), 39–50.
  * Phan et al. (2018) Quoc-Tin Phan, Cecilia Pasquini, Giulia Boato, and Francesco G.B. De Natale. 2018.  Identifying Image Provenance: An Analysis of Mobile Instant Messaging Apps. In _2018 IEEE 20th International Workshop on Multimedia Signal Processing (MMSP)_. 1–6.  https://doi.org/10.1109/MMSP.2018.8547050
  * Popescu and Farid (2004) Alin C Popescu and Hany Farid. 2004.  Statistical tools for digital forensics. In _International workshop on information hiding_. Springer, 128–147.
  * Popescu and Farid (2005) Alin C Popescu and Hany Farid. 2005.  Exposing digital forgeries in color filter array interpolated images.  _IEEE Transactions on Signal Processing_ 53, 10 (2005), 3948–3959.
  * Project Origin (2020) Project Origin. 2020\.  Project Origin - Protecting Trusted Media.  https://www.originproject.info/.
  * Ramesh et al. (2021) Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. 2021\.  Zero-shot text-to-image generation. In _International Conference on Machine Learning_. PMLR, 8821–8831.
  * Ranganath et al. (2013) Suhas Ranganath, Pritam Gundecha, and Huan Liu. 2013\.  A Tool for Assisting Provenance Search in Social Media. In _Proceedings of the 22nd ACM International Conference on Information & Knowledge Management_ (San Francisco, California, USA) _(CIKM ’13)_. Association for Computing Machinery, New York, NY, USA, 2517–2520.  https://doi.org/10.1145/2505515.2508214
  * Resende et al. (2019) Gustavo Resende, Philipe Melo, Hugo Sousa, Johnnatan Messias, Marisa Vasconcelos, Jussara Almeida, and Fabrício Benevenuto. 2019\.  (Mis)Information Dissemination in WhatsApp: Gathering, Analyzing and Countermeasures. In _The World Wide Web Conference_ (San Francisco, CA, USA) _(WWW ’19)_. Association for Computing Machinery, New York, NY, USA, 818–828.  https://doi.org/10.1145/3308558.3313688
  * Riggio et al. (1987) Ronald E Riggio, Joan Tucker, and Barbara Throckmorton. 1987\.  Social skills and deception ability.  _Personality and Social Psychology Bulletin_ 13, 4 (1987), 568–577.
  * Rombach et al. (2022) Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. 2022\.  High-resolution image synthesis with latent diffusion models. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 10684–10695.
  * Rozsa et al. (2020) Andras Rozsa, Zheng Zhong, and Terrance E Boult. 2020\.  Adversarial attack on deep learning-based splice localization. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_. 648–649.
  * Ryan (2013) Mark D. Ryan. 2013\.  Enhanced certificate transparency and end-to-end encrypted mail.  Cryptology ePrint Archive, Paper 2013/595.  https://eprint.iacr.org/2013/595 https://eprint.iacr.org/2013/595.
  * Sacchi et al. (2007) Dario LM Sacchi, Franca Agnoli, and Elizabeth F Loftus. 2007\.  Changing history: Doctored photographs affect memory for past public events.  _Applied Cognitive Psychology: The Official Journal of the Society for Applied Research in Memory and Cognition_ 21, 8 (2007), 1005–1022.
  * Saeed et al. (2022) Mohammed Saeed, Nicolas Traub, Maelle Nicolas, Gianluca Demartini, and Paolo Papotti. 2022\.  Crowdsourced Fact-Checking at Twitter: How Does the Crowd Compare With Experts?. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_ (Atlanta, GA, USA) _(CIKM ’22)_. Association for Computing Machinery, New York, NY, USA, 1736–1746.  https://doi.org/10.1145/3511808.3557279
  * Seo et al. (2019) Haeseung Seo, Aiping Xiong, and Dongwon Lee. 2019\.  Trust It or Not: Effects of Machine-Learning Warnings in Helping Individuals Mitigate Misinformation. In _Proceedings of the 10th ACM Conference on Web Science_ (Boston, Massachusetts, USA) _(WebSci ’19)_. Association for Computing Machinery, New York, NY, USA, 265–274.  https://doi.org/10.1145/3292522.3326012
  * Shen et al. (2019) Cuihua Shen, Mona Kasra, Wenjing Pan, Grace A Bassett, Yining Malloch, and James F O’Brien. 2019\.  Fake images: The effects of source, intermediary, and digital media literacy on contextual assessment of image credibility online.  _New media & society_ 21, 2 (2019), 438–463.
  * Sherchan et al. (2013) Wanita Sherchan, Surya Nepal, and Cecile Paris. 2013\.  A Survey of Trust in Social Networks.  _ACM Comput. Surv._ 45, 4, Article 47 (aug 2013), 33 pages.  https://doi.org/10.1145/2501654.2501661
  * Sherman et al. (2021) Imani N. Sherman, Jack W. Stokes, and Elissa M. Redmiles. 2021\.  _Designing Media Provenance Indicators to Combat Fake Media_.  Association for Computing Machinery, New York, NY, USA, 324–339.  https://doi.org/10.1145/3471621.3471860
  * Sidnam-Mauch et al. (2022) Emily Sidnam-Mauch, Bernat Ivancsics, Ayana Monroe, Eve Washington, Errol Francis II, Kelly Caine, Joseph Bonneau, and Susan E. McGregor. 2022\.  Usable Cryptographic Provenance: A Proactive Complement to Fact-Checking for Mitigating Misinformation. In _Workshop Proceedings of the 16th International AAAI Conference on Web and Social Media_.
  * Soprano et al. (2021) Michael Soprano, Kevin Roitero, David La Barbera, Davide Ceolin, Damiano Spina, Stefano Mizzaro, and Gianluca Demartini. 2021.  The many dimensions of truthfulness: Crowdsourcing misinformation assessments on a multidimensional scale.  _Information Processing & Management_ 58, 6 (2021), 102710\.
  * Stamm and Liu (2010) Matthew C Stamm and KJ Ray Liu. 2010.  Forensic estimation and reconstruction of a contrast enhancement mapping.. In _ICASSP_. Citeseer, 1698–1701.
  * Starling Lab (2022) Starling Lab. 2022\.  Starling Lab.  https://www.starlinglab.org/.
  * Strange et al. (2011) Deryn Strange, Maryanne Garry, Daniel M Bernstein, and D Stephen Lindsay. 2011.  Photographs cause false memories for the news.  _Acta Psychol._ 136, 1 (Jan. 2011), 90–94.
  * Stransky et al. (2021) Christian Stransky, Dominik Wermke, Johanna Schrader, Nicolas Huaman, Yasemin Acar, Anna Lena Fehlhaber, Miranda Wei, Blase Ur, and Sascha Fahl. 2021\.  On the Limited Impact of Visualizing Encryption: Perceptions of E2E Messaging Security. In _Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021)_. USENIX Association, 437–454.  https://www.usenix.org/conference/soups2021/presentation/stransky
  * The Observers (2018) The Observers. 2018\.  Why the way an image is cropped can change everything.  https://observers.france24.com/en/20180824-verification-guide-cropped-photo-video.
  * TinEye (2022) TinEye. 2022.  TinEye Reverse Image Search.  https://tineye.com/.
  * Twitter Developer Platform (2022) Twitter Developer Platform. 2022\.  Summary Card.  https://developer.twitter.com/en/docs/twitter-for-websites/cards/overview/summary.
  * Twitter Help Center (2022a) Twitter Help Center. 2022a.  About Birdwatch on Twitter.  https://help.twitter.com/en/using-twitter/birdwatch.
  * Twitter Help Center (2022b) Twitter Help Center. 2022b.  Synthetic and manipulated media policy.  https://help.twitter.com/en/rules-and-policies/manipulated-media.
  * Tyagi et al. (2021) Nirvan Tyagi, Ben Fisch, Joseph Bonneau, and Stefano Tessaro. 2021\.  Client-Auditable Verifiable Registries.  Cryptology ePrint Archive, Paper 2021/627.  https://eprint.iacr.org/2021/627 https://eprint.iacr.org/2021/627.
  * U.S. Census Bureau (2021) U.S. Census Bureau. 2021\.  Data.  https://www.census.gov/data.html.  Accessed: 2022-03-18.
  * W3C (2013) W3C. 2013.  PROV-Overview.  https://www.w3.org/TR/prov-overview/.
  * Wade et al. (2002) Kimberley A Wade, Maryanne Garry, J Don Read, and D Stephen Lindsay. 2002.  A picture is worth a thousand lies: Using false photographs to create false childhood memories.  _Psychonomic bulletin & review_ 9, 3 (2002), 597–603.
  * Wen et al. (2016) Bihan Wen, Ye Zhu, Ramanathan Subramanian, Tian-Tsong Ng, Xuanjing Shen, and Stefan Winkler. 2016\.  COVERAGE — A novel database for copy-move forgery detection. In _2016 IEEE International Conference on Image Processing (ICIP)_. 161–165.  https://doi.org/10.1109/ICIP.2016.7532339
  * Wu and Liu (2018) Liang Wu and Huan Liu. 2018\.  Tracing Fake-News Footprints: Characterizing Social Media Messages by How They Propagate _(WSDM ’18)_. Association for Computing Machinery, New York, NY, USA, 637–645.  https://doi.org/10.1145/3159652.3159677
  * Wu et al. (2018) Yue Wu, Wael Abd-Almageed, and Prem Natarajan. 2018\.  Image Copy-Move Forgery Detection via an End-to-End Deep Neural Network. In _2018 IEEE Winter Conference on Applications of Computer Vision (WACV)_. 1907–1915.  https://doi.org/10.1109/WACV.2018.00211
  * Yaqub et al. (2020) Waheeb Yaqub, Otari Kakhidze, Morgan L. Brockman, Nasir Memon, and Sameer Patil. 2020\.  _Effects of Credibility Indicators on Social Media News Sharing Intent_.  Association for Computing Machinery, New York, NY, USA, 1–14.  https://doi.org/10.1145/3313831.3376213
  * Yazici and Aktas (2021) Ilkay Melek Yazici and Mehmet S Aktas. 2021.  A Usability Study on Data Provenance Visualization Approaches. In _2021 15th Turkish National Software Engineering Symposium (UYMS)_. IEEE, 1–6.
  * Yazici et al. (2018) Ilkay Melek Yazici, Erkan Karabulut, and Mehmet S Aktas. 2018\.  A Data Provenance Visualization Approach. In _2018 14th International Conference on Semantics, Knowledge and Grids (SKG)_. IEEE, 84–91.
  * Yu et al. (2015) Jiangshan Yu, Mark Ryan, and Cas Cremers. 2015.  How to detect unauthorised usage of a key.  _IACR Cryptol. ePrint Arch._ 2015 (2015), 486.
  * Zhang et al. (2018) Amy X. Zhang, Aditya Ranganathan, Sarah Emlen Metz, Scott Appling, Connie Moon Sehat, Norman Gilmore, Nick B. Adams, Emmanuel Vincent, Jennifer Lee, Martin Robbins, Ed Bice, Sandro Hawke, David Karger, and An Xiao Mina. 2018\.  A Structured Response to Misinformation: Defining and Annotating Credibility Indicators in News Articles. In _Companion Proceedings of the The Web Conference 2018_ (Lyon, France) _(WWW ’18)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 603–612.  https://doi.org/10.1145/3184558.3188731
  * Zhang et al. (2014) Kem ZK Zhang, Sesia J Zhao, Christy MK Cheung, and Matthew KO Lee. 2014.  Examining the influence of online reviews on consumers’ decision-making: A heuristic–systematic model.  _Decision Support Systems_ 67 (2014), 78–89.
  * Zhang (2012) Michael Zhang. 2012\.  The Kent State Massacre Photo and the Case of the Missing Pole.  https://petapixel.com/2012/08/29/the-kent-state-massacre-photo-and-the-case-of-the-missing-pole/.
  * Zhou et al. (2018) Peng Zhou, Xintong Han, Vlad I Morariu, and Larry S Davis. 2018\.  Learning rich features for image manipulation detection. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 1053–1061.

##  Appendix A All Media Used

Figure 8. The 12 pieces of media used in the study. ID |  Topic |  Edit Status |  State |  Claim |  Claim Agreement |  Image/ Video |  Region
---|---|---|---|---|---|---|---
1 |  News |  Non-composited |  Incomplete |  This is an artistic rendering of cells in the human immune system. |  Agree |  Image |  Both
2 |  Lifestyle |  Non-composited |  Normal |  This is a real photo that captures a meteor falling into an active volcano. |  Disagree |  Image |  Both
3 |  Lifestyle |  Composited |  Normal |  This is a real video that shows a dog narrowly escaping an alligator pit. |  Disagree |  Video |  Both
4 |  Lifestyle |  Non-composited |  Normal |  This is a real photo of a ”triple-neck” guitar owned by Led Zeppelin bassist John Paul Jones. |  Agree |  Image |  Both
5 |  News |  Non-composited |  Invalid |  This is a real photo showing some trucks on an empty street in Myanmar. |  Agree |  Image |  Both
6 |  National |  Composited |  Incomplete |  This is a real photo showing Eric Trump holding a shovel backwards. |  Disagree |  Image |  US
7 |  National |  Composited |  Incomplete |  This is a real photo showing a dog defecating on the steps of 10 Downing Street. |  Disagree |  Image |  UK
8 |  National |  Non-composited |  Invalid |  Germany, China, and other countries created a ”Great Nations Eat” campaign to feed hungry Americans. |  Disagree |  Video |  US
9 |  National |  Non-composited |  Invalid |  CNN created ”fake news” and staged protests in which Muslim residents purportedly protested a 3 June 2017 attack in London. |  Disagree |  Video |  UK
10 |  National |  Non-composited |  Normal |  This is a real photo that shows a 740’ x 390’ floral flag made of larkspur. |  Agree |  Image |  US
11 |  National |  Non-composited |  Normal |  This is a real historical photograph that shows British troops in drag pointing a naval gun at incoming Nazi planes. |  Agree |  Image |  UK
12 |  News |  Non-composited |  Normal |  This is a real radio-wave image of the Milky Way’s center. |  Agree |  Image |  Both
Table 8. Table of all media used (IDs in Fig. 8) with their respective media
properties.

##  Appendix B Demographic Breakdown by Region

Demographics (US) |  Percentage ($n=298$)
---|---
Age
18–24 |  16
25–44 |  47
45–65 |  37
Highest Education Obtained
High school or below |  30
Associate’s degree/vocational training |  14
Bachelor’s degree |  37
Master’s/professional degree |  17
Ph.D. |  2
Annual Household Income (USD)
¡ 30,000 |  25
30,000–59.999 |  24
60,000–89,999 |  19
90,000–149,999 |  17
150,000+ |  13
Decline to Respond |  2
Political Affiliation
Liberal |  26
Liberal-leaning |  16
Moderate |  18
Conservative-leaning |  23
Conservative |  16
Race
Asian |  4
Black/African American |  9
Mixed |  4
Native American/Pacific Islander |  1
White |  81
Other/Decline to Respond |  1
Gender
Woman |  52
Man |  46
Non-binary / third gender |  2
Table 9. Demographics of US participants.

Demographics (UK) |  Percentage ($n=297$)
---|---
Age
18–24 |  13
25–44 |  43
45–65 |  44
Highest Education Obtained
High school or below |  41
Associate’s degree/vocational training |  17
Bachelor’s degree |  29
Master’s/professional degree |  10
Ph.D. |  3
Annual Household Income (GBP)
¡ 20,000 |  22
20,000–39.999 |  32
40,000–59,999 |  20
60,000–99,999 |  9
100,000+ |  2
Decline to Respond |  15
Political Affiliation
Left wing |  14
Centre-left |  23
Centre |  39
Centre-right |  20
Right wing |  4
Race
Asian |  5
Black |  3
Mixed |  2
White |  89
Other/Decline to Respond |  1
Gender
Woman |  53
Man |  46
Non-binary / third gender |  0.3
Prefer not to disclose |  0.7
Table 10. Demographics of UK participants.

##  Appendix C Provenance Indicator Design and Language Variations

Figure 9. Our 18 variations of provenance indicators across no-state and
mixed-state feeds. The split icons in the mixed-state section indicates that
the icon can be either the normal, incomplete, or invalid one.

##  Appendix D Survey Screenshots

Figure 10. Intro page. Figure 11. Preliminary questions about social media
usage patterns. Figure 12. First round of media evaluations. Figure 13.
Graphical debrief between first and second rounds of media evaluations. Figure
14. Second round of media evaluations. Figure 15. Exit survey part 1:
capturing comprehension and feedback. Figure 16. Exit survey part 2:
demographics.


for all $f\in\mathcal{F}_{\gamma}$, the third equation arise from the
definition that
$\mathbb{O}_{\gamma}(\cdot|s)=f_{\gamma}(\cdot,s)\cdot\mathcal{P}^{-}(\cdot)$,
and we write $\mathbb{\bar{O}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)=\frac{1}{2}\left(\mathbb{O}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)+\mathcal{P}^{-}(\cdot)\right),\mathbb{\bar{O}}_{{\gamma}}(\cdot\hskip
1.42262pt|\hskip
1.42262pts)=\frac{1}{2}\left(\mathbb{O}_{{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)+\mathcal{P}^{-}(\cdot)\right)$. Moreover,
$\mathbb{\bar{O}}(\cdot|s)$ represents the marginal distribution derived from
the joint distribution $\mathbb{P}_{\mathcal{C}}$ of collected dataset
$\mathcal{D}_{\mathtt{Rep}}$ (see data collection process in §3.2), as
follows:

$\displaystyle\mathbb{P}_{\mathcal{C}}(o\hskip 1.42262pt|\hskip 1.42262pts)$
$\displaystyle=\mathbb{P}_{\mathcal{C}}(o\hskip 1.42262pt|\hskip
1.42262pts,y=0)\cdot\mathbb{P}_{\mathcal{C}}(y=0\hskip 1.42262pt|\hskip
1.42262pts)+\mathbb{P}_{\mathcal{C}}(o\hskip 1.42262pt|\hskip
1.42262pts,y=1)\cdot\mathbb{P}_{\mathcal{C}}(y=1\hskip 1.42262pt|\hskip
1.42262pts)$ $\displaystyle=\mathbb{P}_{\mathcal{C}}(o\hskip 1.42262pt|\hskip
1.42262pts,y=0)\cdot\mathbb{P}_{\mathcal{C}}(y=0)+\mathbb{P}_{\mathcal{C}}(o\hskip
1.42262pt|\hskip
1.42262pts,y=1)\cdot\mathbb{P}_{\mathcal{C}}(y=1):=\mathbb{\bar{O}}(o\hskip
1.42262pt|\hskip 1.42262pts),$ (D.3)

where the second equation results from the fact that contrastive data are
labeled independent of data itself such that $\mathbb{P}_{\mathcal{C}}(s\hskip
1.42262pt|\hskip 1.42262pty)=\mathbb{P}_{\mathcal{C}}(s)$ for all
$y\in\\{0,1\\}$. Based on (D.3), we can get

$\displaystyle\bar{\mathbb{E}}_{(o,s)\sim\mathcal{D}_{\mathtt{Rep}}}\left[\left(\frac{\mathbb{\bar{O}}_{\widehat{\gamma}}(o\hskip
1.42262pt|\hskip 1.42262pts)-\mathbb{\bar{O}}(o\hskip 1.42262pt|\hskip
1.42262pts)}{\mathbb{\bar{O}}(o\hskip 1.42262pt|\hskip
1.42262pts)}\right)^{2}\right]=\bar{\mathbb{E}}_{s\sim\mathcal{D}_{\mathtt{Rep}}}\left[\mathbb{E}_{o\sim\mathbb{\bar{O}}(\cdot\hskip
1.42262pt|\hskip
1.42262pts)}\left[\left(\frac{\mathbb{\bar{O}}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)-\mathbb{\bar{O}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)}{\mathbb{\bar{O}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)}\right)^{2}\right]\right],$ (D.4)

where equations results from the fact that
$\mathbb{P}_{\mathcal{C}}(o,s)=\mathbb{\bar{O}}(o\hskip 1.42262pt|\hskip
1.42262pts)\cdot\mathbb{P}_{\mathcal{C}}(s)$ and definition of
$\chi^{2}$-divergence. Therefore, combine (D.2) and (D.4), it holds that

$\displaystyle\bar{\mathbb{E}}_{(o,s)\sim\mathcal{D}_{\mathtt{Rep}}}\left[D_{\rm
TV}^{2}\left(\mathbb{D}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s),\mathbb{D}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s)\right)\right]\leq\frac{1}{(1+R_{\mathcal{F}})^{2}}\cdot\bar{\mathbb{E}}_{s\sim\mathcal{D}_{\mathtt{Rep}}}\left[\chi^{2}\left(\mathbb{\bar{O}}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{\bar{O}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)\right)\right].$ (D.5)

Based on the variational representation of $f$-divergenve (§7.13, Polyanskiy
and Wu,, 2022), we have

$\displaystyle\chi^{2}\left(\mathbb{\bar{O}}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{\bar{O}}(\cdot\hskip 1.42262pt|\hskip 1.42262pts)\right)$
$\displaystyle=\sup_{g:\mathcal{O}\mapsto\mathbb{R}}\left\\{\frac{\left(\mathbb{E}_{\mathbb{\bar{O}}_{\widehat{\gamma}}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]-\mathbb{E}_{\mathbb{\bar{O}}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]\right)^{2}}{{\rm
Var}_{\mathbb{\bar{O}}}[g(o)\hskip 1.42262pt|\hskip 1.42262pts]}\right\\}$
$\displaystyle=\sup_{g:\mathcal{O}\mapsto\mathbb{R}}\left\\{\frac{\left(\mathbb{E}_{\mathbb{O}_{\widehat{\gamma}}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]-\mathbb{E}_{\mathbb{O}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]\right)^{2}}{4\cdot{\rm
Var}_{\mathbb{O}}[g(o)\hskip 1.42262pt|\hskip 1.42262pts]}\cdot\frac{{\rm
Var}_{\mathbb{O}}[g(o)\hskip 1.42262pt|\hskip 1.42262pts]}{{\rm
Var}_{\mathbb{\bar{O}}}[g(o)\hskip 1.42262pt|\hskip 1.42262pts]}\right\\}$
$\displaystyle\geq\sup_{\begin{subarray}{c}g:\mathcal{O}\mapsto\mathbb{R},\\\
\mathbb{E}_{\mathbb{O}}[g(o)|s]=0\end{subarray}}\left\\{\frac{\left(\mathbb{E}_{\mathbb{O}_{\widehat{\gamma}}}[g(o)|s]-\mathbb{E}_{\mathbb{O}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]\right)^{2}}{4\cdot{\rm
Var}_{\mathbb{O}}[g(o)\hskip 1.42262pt|\hskip
1.42262pts]}\cdot\frac{\mathbb{E}_{\mathbb{O}}[g(o)^{2}\hskip 1.42262pt|\hskip
1.42262pts]}{\mathbb{E}_{\mathbb{\bar{O}}}[g(o)^{2}\hskip 1.42262pt|\hskip
1.42262pts]}\right\\},$ (D.6)

where the second equation follows the defintions of
$\mathbb{\bar{O}}(\cdot\hskip 1.42262pt|\hskip 1.42262pts)$ and
$\mathbb{\bar{O}}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)$, and the inequality results from ${\rm
Var}_{\mathbb{\bar{O}}}[g(o)|s]=\mathbb{E}_{\mathbb{\bar{O}}}[g(o)^{2}|s]$ if
$\mathbb{E}_{\mathbb{O}_{\widehat{\gamma}}}[g(o)|s]$=0. Furthermore, note that

$\displaystyle\frac{\mathbb{E}_{\mathbb{O}}[g(o)^{2}\hskip 1.42262pt|\hskip
1.42262pts]}{\mathbb{E}_{\mathbb{\bar{O}}}[g(o)^{2}\hskip 1.42262pt|\hskip
1.42262pts]}$
$\displaystyle=2\left(1+\frac{\mathbb{E}_{\mathcal{P}^{-}}[g(o)^{2}\hskip
1.42262pt|\hskip 1.42262pts]}{\mathbb{E}_{\mathbb{O}}[g(o)^{2}\hskip
1.42262pt|\hskip 1.42262pts]}\right)^{-1}\leq
2\left(1+\left\|\frac{\mathcal{P}^{-}(\cdot)}{\mathbb{O}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)}\right\|_{\infty}\right)^{-1}\leq
2(1+B^{-}_{\mathcal{F}})^{-1},$ (D.7)

as $\mathcal{P}^{-}(\cdot)/\mathbb{P}(\cdot|s)=f^{*}\in\mathcal{F}_{\gamma}$
and $\|1/f\|_{\infty}\leq B^{-}_{\mathcal{F}}$ for all $f\in\mathcal{F}$ under
the realizability in Assumption 5.4. Besides, it holds that

$\displaystyle\sup_{\begin{subarray}{c}g:\mathcal{O}\mapsto\mathbb{R},\\\
\mathbb{E}_{\mathbb{O}}[g(o)|s]=0\end{subarray}}\left\\{\frac{\left(\mathbb{E}_{\mathbb{O}_{\widehat{\gamma}}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]-\mathbb{E}_{\mathbb{O}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]\right)^{2}}{{\rm Var}_{\mathbb{O}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]}\right\\}$
$\displaystyle=\sup_{g:\mathcal{O}\mapsto\mathbb{R}}\left\\{\frac{\left(\mathbb{E}_{\mathbb{O}_{\widehat{\gamma}}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]-\mathbb{E}_{\mathbb{O}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]\right)^{2}}{{\rm Var}_{\mathbb{O}}[g(o)\hskip
1.42262pt|\hskip 1.42262pts]}\right\\}$
$\displaystyle=\chi^{2}\left(\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{O}(\cdot\hskip 1.42262pt|\hskip 1.42262pts)\right),$ (D.8)

Based on (D.1), (D.5), (D.6), (D.7) and (D.8), then we have

$\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{Rep}}}\left[\chi^{2}\left(\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{O}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)\right)\right]\leq\mathcal{O}\left(\frac{(1+B^{-}_{\mathcal{F}})(1+B_{\mathcal{F}})^{2}}{N_{\rm
p}T_{\rm p}H}\cdot\log(N_{\rm p}T_{\rm p}H|\mathcal{F}|/\delta)\right).$ (D.9)

Combine (D.9) and the divergence inequalities (§7.6, Polyanskiy and Wu,,
2022), we have

$\displaystyle\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{Rep}}}\left[D_{\rm
TV}\left(\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)\hskip 1.42262pt\|\hskip 1.42262pt\mathbb{O}(\cdot\hskip
1.42262pt|\hskip
1.42262pts)\right)\right]\leq\frac{1}{2}\cdot\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{Rep}}}\left[\sqrt{\chi^{2}\left(\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{O}(\cdot\hskip 1.42262pt|\hskip 1.42262pts)\right)}\right]$
$\displaystyle\hskip
14.22636pt\leq\frac{1}{2}\cdot\sqrt{\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{Rep}}}\left[\chi^{2}\left(\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{O}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)\right)\right]}\leq\mathcal{O}\left(\frac{B_{\mathcal{F}}(B^{-}_{\mathcal{F}})^{1/2}}{(N_{\rm
p}T_{\rm p}H)^{1/2}}\sqrt{\log(N_{\rm p}T_{\rm
p}H|\mathcal{F}_{\gamma}|/\delta)}\right),$

where the second inequality follows
$\mathbb{E}[X]\leq\sqrt{\mathbb{E}[X^{2}]}$ and we finish the proof of Theorem
5.5. $\Box$

###  D.2 Proof of Theorem 5.7

#### Notations.

Denote $(\mathcal{J},\mathcal{\widehat{J}})$,
$({\pi}_{z}^{*},\widehat{\pi}_{z}^{*})$, and
$(\mathbb{P}_{z,h},\mathbb{\widehat{P}}_{z,h})$ as the value functions,
optimal policies, and probability distributions under the environment
concerning the ground-truth $\mathbb{O}$ and the pretrained
$\mathbb{O}_{\widehat{\gamma}}$. Furthermore, $(\pi^{t},\widehat{\pi}^{t})$
are the Planner’s policy empowered by perfect $\mathtt{LLM}$ or pretrained
$\mathtt{LLM}_{\widehat{\theta}}$.
_Proof of Theorem 5.7._ Conditioned on the event $\mathcal{E}_{1}$ that both
Theorem 2 and 5.5 hold, the regret under the practical setting can be
decomposed as

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle\leq\underbrace{\sum_{t=1}^{T}\mathcal{\widehat{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})}_{\textbf{(i})}+\underbrace{\sum_{t=1}^{T}\mathcal{{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{{J}}_{z}({\pi}_{z}^{*},\omega^{t})}_{\textbf{(ii})}$
$\displaystyle\quad+\underbrace{\sum_{t=1}^{T}\mathcal{{J}}_{z}({\pi}_{z}^{*},\omega^{t})-\mathcal{\widehat{J}}_{z}({\pi}_{z}^{*},\omega^{t})}_{\textbf{(iii})}+\underbrace{\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{z}({\pi}_{z}^{*},\omega^{t})-\mathcal{\widehat{J}}_{z}(\widehat{\pi}^{t},\omega^{t})\right]}_{\textbf{(iv})},$
(D.10)

and $\textbf{(ii})\leq 0$ results from the optimality such that
$\mathcal{{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})\leq\mathcal{{J}}_{z}({\pi}_{z}^{*},\omega^{t})$
for all $t\in[T]$.

Step 1. Bound (i) and (iii) with Translator’s Pretraining Error.
For any policy sequence $\\{\pi_{t}\\}_{t\leq T}\subseteq\Pi$ and length
$T\in\mathbb{N}$, based on PDL in Lemma F.4, we have

$\displaystyle\sum_{t=1}^{T}\mathcal{\widehat{J}}_{z}(\pi_{t},\omega^{t})-\mathcal{{J}}_{z}(\pi_{t},\omega^{t})$
$\displaystyle\quad=\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t},g_{h}^{t})\sim\mathbb{P}_{z}^{\pi_{t}}}\left[(\mathbb{P}_{z,h}\widehat{V}_{h}^{\pi_{t}}-\mathbb{\widehat{P}}_{z,h}\widehat{V}_{h}^{\pi_{t}})(s_{h}^{t},\tau_{h}^{t},g_{h}^{t},\omega^{t})\right]$
$\displaystyle\quad\leq
H\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t},g_{h}^{t})\sim\mathbb{P}_{z}^{\pi_{t}}}\left[D_{\rm
TV}\left(\mathbb{P}_{z,h}(\cdot,\cdot\hskip 1.42262pt|\hskip
1.42262pts_{h}^{t},\tau_{h}^{t},g_{h}^{t}),\mathbb{\widehat{P}}_{z,h}(\cdot,\cdot\hskip
1.42262pt|\hskip 1.42262pts_{h}^{t},g_{h}^{t},\tau_{h}^{t})\right)\right]$
$\displaystyle\quad\leq
H\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{(s_{h}^{t},g_{h}^{t})\sim\mathbb{P}_{z}^{\pi_{t}}}\mathbb{E}_{s_{h+1}^{t}\sim\mathbb{P}_{z,h}(\cdot\hskip
1.42262pt|\hskip 1.42262pts_{h}^{t},g_{h}^{t})}\left[D_{\rm
TV}\left(\mathbb{O}(\cdot|s_{h+1}^{t}),\mathbb{O}_{\widehat{\gamma}}(\cdot|s_{h+1}^{t})\right)\right],$
(D.11)

where the last inequality results from the fact that for any $f$-divergence,
it holds that

$D_{f}(\mathbb{P}_{Y|X}\otimes\mathbb{P}_{X},\mathbb{Q}_{Y|X}\otimes\mathbb{P}_{X})=\mathbb{E}_{X\sim\mathbb{P}_{X}}[D_{f}(\mathbb{P}_{Y|X},\mathbb{Q}_{Y|X})].$

Based on (D.11), by taking policies $\pi=\widehat{\pi}_{z}^{*}$ and
$\pi={\pi}_{z}^{*}$ respectively, we have

$\displaystyle\textbf{\small(i})+\textbf{\small(iii})$
$\displaystyle=\sum_{t=1}^{T}\mathcal{\widehat{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})+\sum_{t=1}^{T}\mathcal{{J}}_{z}({\pi}_{z}^{*},\omega^{t})-\mathcal{\widehat{J}}_{z}({\pi}_{z}^{*},\omega^{t})$
$\displaystyle\leq 2H^{2}T\cdot\max_{s\in\mathcal{S}}\left\\{D_{\rm
TV}\left(\mathbb{O}(\cdot\hskip 1.42262pt|\hskip
1.42262pts),\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)\right)\right\\}\leq
2H^{2}T\lambda_{R}^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta),$ (D.12)

where the last inequality results from Assumption 5.6 and Theorem 5.5.
Step 2. Bound (iv) with LLM’s and Translator’s Pretraining Errors
Recall that the Planner follows a mixture policy of $\pi_{\mathtt{exp}}$ and
$\widehat{\pi}_{\mathtt{LLM}}$ as

$\pi_{h}^{t}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})\sim(1-\epsilon)\cdot\widehat{\pi}_{h,\mathtt{LLM}}^{t}(\cdot\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})+\epsilon\cdot\pi_{h,\mathtt{exp}}(\cdot|\tau_{h}^{t}).$
(D.13)

Based on PDL in Lemma F.4, the performance difference in term (iv) can be
decomposed as

$\displaystyle\textbf{\small(iv})$
$\displaystyle=\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[(\pi^{*}_{z,h}-\widehat{\pi}_{h}^{t})\widehat{Q}_{h}^{\pi_{z}^{*}}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]$
$\displaystyle=\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[\left(\pi^{*}_{z,h}-{\widehat{\pi}^{t}_{h,\mathtt{LLM}}}\right)\widehat{Q}_{h}^{\pi_{z}^{*}}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]\cdot(1-\epsilon)$
$\displaystyle\quad+\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[\left(\pi^{*}_{z,h}-\pi_{h,\mathtt{exp}}\right)\widehat{Q}_{h}^{\pi_{z}^{*}}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]\cdot\epsilon$
$\displaystyle\leq
H\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[D_{\rm
TV}\left(\pi_{z,h}^{*}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}),\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})\right)\right]+HT\epsilon$
(D.14)

where we write
$\pi_{h}Q_{h}(s_{h},\tau_{h},\omega)=\langle\pi_{h}(\cdot|\tau_{h},\omega),Q_{h}(s_{h},\tau_{h},\cdot,\omega)\rangle_{\mathcal{G}}$
for all $h\in[H]$, and $\widehat{Q}_{h}^{\pi}$ denotes the action value
function under the practical setting. Furthermore, we have

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[D_{\rm
TV}\left(\pi_{z,h}^{*}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}),\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t})\right)\right]$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[D_{\rm
TV}\left(\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t}),\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\right)\right]$
$\displaystyle\quad+\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[D_{\rm
TV}\left(\pi_{z,h}^{*}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}),\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\right)\right]$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[D_{\rm
TV}\left(\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t}),\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\right)\right]$
$\displaystyle\quad+\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[\sum_{z^{\prime}\neq
z}\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\right],$ (D.15)

where the first inequality arises from the triangle inequality, and the second
inequality results from Thoerem 4.2. Furthermore, the first term can be
bounded by the pretraining error, following

$\displaystyle\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[D_{\rm
TV}\left(\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t}),\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\right)\right]$
$\displaystyle\quad\leq\lambda_{S}\cdot\sum_{t=1}^{T}\sum_{h=1}^{H}\bar{\mathbb{E}}_{\mathtt{pt}_{h}^{t}\sim\mathcal{D}_{\mathtt{LLM}}}\left[D_{\rm
TV}\left(\mathtt{LLM}_{\widehat{\theta}}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t}),\mathtt{LLM}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\right)\right],$
$\displaystyle\quad=\lambda_{S}HT\cdot\Delta_{\mathtt{LLM}}(N_{\rm p},T_{\rm
p},H,\delta),$ (D.16)

where the last inequality follows Theorem 2 and Assumption 5.6. Under
practical setting, $\mathtt{pt}_{h}^{t}$ is generated from practical
transition $\mathbb{\widehat{P}}_{z}$, mismatching
$\mathbb{P}_{\mathcal{D}}(z\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})$ in pretraining. Let
$\mathcal{X}^{t}_{\mathtt{exp}}=\\{i\in[t]:\widehat{\pi}^{i}=\pi_{\mathtt{exp}}\\}$
and write $\breve{\tau}_{h/t}^{i}={\tau}_{H}^{i}$ for all $i<t$ and
$\breve{\tau}_{h/t}^{t}={\tau}_{h}^{t}$. Define the information gains as

$L_{h,t}^{\mathtt{exp}}(z^{\prime})=\sum_{i\in\mathcal{X}^{t}_{\mathtt{exp}}}\log\left(\frac{\mathbb{P}_{z^{\prime}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}(\breve{\tau}_{h/t}^{i})}\right),\quad
L_{h,t}^{\mathtt{LLM}}(z^{\prime})=\sum_{i\in[t]\backslash\mathcal{X}^{t}_{\mathtt{exp}}}\log\left(\frac{\mathbb{P}_{z^{\prime}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}(\breve{\tau}_{h/t}^{i})}\right),$
(D.17)

where $\mathbb{P}_{z}(\tau_{h})$ is defined in (A.3). Based on the law of
total probability, we have

$\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})=\frac{\mathbb{P}_{z^{\prime}}(\mathtt{pt}_{h}^{t})\cdot\mathcal{P}_{\mathcal{Z}}(z^{\prime})}{\sum_{\tilde{z}\in\mathcal{Z}}\mathbb{P}_{\tilde{z}}(\mathtt{pt}_{h}^{t})\cdot\mathcal{P}_{\mathcal{Z}}(\tilde{z})}\leq\frac{\mathbb{P}_{z^{\prime}}(\mathtt{pt}_{h}^{t})}{\mathbb{P}_{z}(\mathtt{pt}_{h}^{t})}\cdot\frac{\mathcal{P}_{\mathcal{Z}}(z^{\prime})}{\mathcal{P}_{\mathcal{Z}}(z)}.$
(D.18)

Let $\mathcal{E}_{2}$ be the event that Lemma D.1 holds. Based on (D.18),
(D.17) and conditioned on event $\mathcal{E}_{2}$, it holds that

$\displaystyle\sum_{z^{\prime}\neq z}\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\leq\min\left\\{\sum_{z^{\prime}\neq
z}\frac{\mathbb{P}_{z^{\prime}}(\mathtt{pt}_{h}^{t})}{\mathbb{P}_{z}(\mathtt{pt}_{h}^{t})}\cdot\frac{\mathcal{P}_{\mathcal{Z}}(z^{\prime})}{\mathcal{P}_{\mathcal{Z}}(z)},1\right\\}$
$\displaystyle\leq\min\left\\{c_{\mathcal{Z}}\sum_{z^{\prime}\neq
z}\exp\left(L_{h,t}^{\mathtt{exp}}(z^{\prime})+L_{h,t}^{\mathtt{LLM}}(z^{\prime})\right),1\right\\}$
$\displaystyle\leq\min\left\\{c_{\mathcal{Z}}\sum_{z^{\prime}\neq
z}\exp\Big{(}t\cdot H\lambda^{-1}_{R}\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)^{2}-2\eta|\mathcal{X}^{t}_{\mathtt{exp}}|+8\log(|\mathcal{Z}|/\delta)+2\eta\Big{)},1\right\\}$
$\displaystyle\leq\min\left\\{c_{\mathcal{Z}}\sum_{z^{\prime}\neq
z}\exp\Big{(}-\left(\eta\epsilon-H\lambda^{-1}_{R}\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm
p},H,\delta)^{2}\right)t+8\log(|\mathcal{Z}|/\delta)+2\eta\Big{)},1\right\\}$
$\displaystyle\leq\min\left\\{c_{\mathcal{Z}}\cdot\exp\Big{(}-\left(\eta\epsilon-H\lambda^{-1}_{R}\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm
p},H,\delta)^{2}\right)t+9\log(|\mathcal{Z}|/\delta)+2\eta\Big{)},1\right\\}$
(D.19)

for all $(h,t)\in[H]\times[T]$, where the second inequality follows Assumption
4.5. Here, we suppose that $|\mathcal{X}^{t}_{\mathtt{exp}}|/t=\epsilon$ for
simplicity, which is attainable if we explore at a fixed fraction during
episodes. Assume that $\eta\epsilon\geq
H\lambda^{-1}_{R}\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm p},H,\delta)^{2}$
holds temporarily. Following (D.19) and condition on event $\mathcal{E}_{2}$,
there exists a large constant $c_{0}>0$ such that

$\displaystyle\sum_{t=1}^{T}$ $\displaystyle\sum_{h=1}^{H}\sum_{z^{\prime}\neq
z}\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\leq c_{0}\cdot
H\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)\cdot\left(\eta\epsilon-H\lambda^{-1}_{R}\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}\right)^{-1},$ (D.20)

where we use the fact that there exists constant $c_{0}>0$ such that
$\sum_{t=1}^{T}\min\\{c_{3}\exp(-c_{1}t+c_{2}),1\\}\leq c_{0}\cdot
c_{1}^{-1}(c_{2}+\log c_{3})$ for $c_{1}\leq 1$. Furthermore, based on (D.20),
we can show that

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[\sum_{z^{\prime}\neq
z}\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\right]$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\sum_{z^{\prime}\neq
z}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{t}}}\left[\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\operatorname{\mathds{1}}\left(\mathcal{E}_{2}\text{~{}holds}\right)\right]+2HT\delta$
$\displaystyle\leq c_{0}\cdot
H\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)\cdot\left(\eta\epsilon-H\lambda^{-1}_{R}\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}\right)^{-1}+2HT\delta.$ (D.21)

Combine (D.14), (D.19), (D.16) and (D.21), it holds that

$\displaystyle\textbf{\small(iv})$ $\displaystyle\leq\underbrace{c_{0}\cdot
H^{2}\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)\cdot\left(\eta\epsilon-H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}\right)^{-1}}_{\textbf{(v})}$
$\displaystyle\qquad+\underbrace{HT\eta^{-1}\left(\eta\epsilon-H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm
p},H,\delta)^{2}\right)}_{\textbf{(vi})}+\lambda_{S}H^{2}T\cdot\Delta_{\mathtt{LLM}}(N_{\rm
p},T_{\rm p},H,\delta)$
$\displaystyle\qquad+H^{2}T(\eta\lambda_{R})^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}+2HT\delta,$ (D.22)

If we explore with probability
$\epsilon=H(\eta\lambda_{R})^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)^{2}+(H\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right)/T\eta)^{1/2}$,
which satisfies the condition that $\eta\epsilon\geq
H\lambda^{-1}_{R}\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm p},H,\delta)^{2}$
assumed in (D.19), then we have

$\displaystyle\textbf{\small(v})+\textbf{\small(vi})\leq\mathcal{O}\left(H^{\frac{3}{2}}\sqrt{\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)\cdot
T/\eta}\right).$ (D.23)

Step 3. Conclude the Proof based on Step 1 and Step 2.
Combine (D.10), (D.12), (D.22) and (D.23), the regret under the practical
setting follows

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle\leq\textbf{\small(i})+\textbf{\small(iii})+\textbf{\small(iv})+HT\cdot\mathbb{P}(\mathcal{E}_{1}\text{~{}fails})$
$\displaystyle=\mathcal{O}\underbrace{\Big{(}H^{\frac{3}{2}}\sqrt{\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)\cdot
T/\eta}}_{\displaystyle\text{Planning
error}}+\underbrace{H^{2}T\cdot\Delta_{\rm p}(N_{\rm p},T_{\rm
p},H,\delta,\xi)\Big{)}}_{\displaystyle\text{Pretraining error}}+4HT\delta,$
(D.24)

where the cumulative pretraining error of the imperfectly pretrained PAR
system follows

$\displaystyle\Delta_{\rm p}$ $\displaystyle(N_{\rm p},T_{\rm
p},H,\delta,\xi)=(\eta\lambda_{R})^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}$
$\displaystyle+2\lambda_{R}^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)+\lambda_{S}\cdot\Delta_{\mathtt{LLM}}(N_{\rm p},T_{\rm
p},H,\delta).$

Here, $\xi=(\eta,\lambda_{S},\lambda_{R})$ denotes the set of
distinguishability and coverage coefficients in Definition 4.4 and Assumption
5.6, and $\Delta_{\mathtt{LLM}}(N_{\rm p},T_{\rm p},H,\delta)$ and
$\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm p},H,\delta)$ are pretraining errors
defined in Theorem 2 and Theorem 5.5. By taking $\delta=1/\sqrt{T}$, we
complete the proof of Theorem 5.7. $\Box$

###  D.3 Proof of Lemma D.1

In this subsection, we provide a detailed examination of posterior
concentration when there exists a mismatch between the ground-truth
environment and the pretrained environment.

######  Lemma D.1.

Suppose that Assumption 4.5 and Theorem 5.5 hold. For all
$(z^{\prime},h,t)\in\mathcal{Z}\times[H]\times[T]$, with probability at least
$1-2\delta$, it holds that

$\displaystyle\qquad\text{(i).}\
L_{h,t}^{\mathtt{LLM}}(z^{\prime})\leq\left(t-|\mathcal{X}^{t}_{\mathtt{exp}}|\right)H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}+4\log(|\mathcal{Z}|/\delta),$
$\displaystyle\qquad\text{(ii).}\
L_{h,t}^{\mathtt{exp}}(z^{\prime})\leq|\mathcal{X}^{t}_{\mathtt{exp}}|H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm
p},H,\delta)^{2}+4\log(|\mathcal{Z}|/\delta)-2\eta\cdot|\mathcal{X}^{t}_{\mathtt{exp}}|+2\eta,$

where $L_{h,t}^{\mathtt{LLM}}(z^{\prime})$ and
$L_{h,t}^{\mathtt{exp}}(z^{\prime})$ are the information gain defined in
(D.17).

_Proof of Lemma D.1_. Let $\mathfrak{F}_{t}$ be the filtration induced by
$\\{\omega^{i},\tau_{H}^{i}\\}_{i<t}\cup\\{\operatorname{\mathds{1}}(\pi^{i}=\pi_{\texttt{exp}})\\}_{i\in[t]}$.
Consider a fixed tuple $(z^{\prime},h,t)\in\mathcal{Z}\times[H]\times[T]$, it
holds that

$\displaystyle\mathbb{\widehat{P}}_{z}(L_{h,t}^{\mathtt{LLM}}(z^{\prime})\geq\beta_{h,t}^{\mathtt{LLM}})\leq\underset{\lambda\geq
0}{\inf}\
\mathbb{E}_{\mathfrak{F}_{1:t}}\left[\exp(\lambda\cdot(L_{h,t}^{\mathtt{LLM}}(z^{\prime})-\beta_{h,t}^{\mathtt{LLM}}))\right]$
$\displaystyle\quad=\underset{\lambda\geq 0}{\inf}\
\mathbb{E}_{\bigotimes_{i\in[t]\backslash\mathcal{X}^{t}_{\mathtt{exp}}}\mathbb{\widehat{P}}_{z}^{\widehat{\pi}_{i}}}\left[\exp\left(\sum_{i\in[t]\backslash\mathcal{X}^{t}_{\mathtt{exp}}}\lambda\cdot\log\left(\frac{\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}\right)-\lambda\cdot\beta_{h,t}^{\mathtt{LLM}}\right)\right]$
$\displaystyle\quad=\underset{\lambda\geq 0}{\inf}\
\prod_{i\in[t]\backslash\mathcal{X}^{t}_{\mathtt{exp}}}\mathbb{E}_{\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}}\left[\left(\frac{\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}{\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}\right)^{\lambda}\cdot\frac{\mathbb{\widehat{P}}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}\right]\cdot\exp\left(-\lambda\cdot\beta_{h,t}^{\mathtt{LLM}}\right)$
$\displaystyle\quad\leq\underset{\lambda\geq 0}{\inf}\
\prod_{i\in[t]\backslash\mathcal{X}^{t}_{\mathtt{exp}}}\mathbb{E}_{\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}}\left[\left(\frac{\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}{\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}\right)^{2\lambda}\right]^{1/2}\mathbb{E}_{\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}}\left[\left(\frac{\mathbb{\widehat{P}}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}\right)^{2}\right]^{1/2}\cdot\exp\left(-\lambda\cdot\beta_{h,t}^{\mathtt{LLM}}\right),$

where the first inequality is a natural corollary to Lemma F.1, and the last
inequality follows the Cauchy-Swartz inequality. By taking
$\lambda=\frac{1}{4}$, for all $(h,t)\in[H]\times[T]$, we have

$\displaystyle\mathbb{E}_{\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}}\left[\left(\frac{\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}{\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}\right)^{1/2}\right]^{1/2}\mathbb{E}_{\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}}\left[\left(\frac{\mathbb{\widehat{P}}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}{\mathbb{P}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})}\right)^{2}\right]^{1/2}\leq\sqrt{1+\chi^{2}\big{(}\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\hskip
1.42262pt\|\hskip
1.42262pt\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}}.$
(D.25)

Based on Theorem 5.5 and Assumption 4.5, for any policy $\pi\in\Pi$, it holds
that

$\displaystyle 1$
$\displaystyle+\chi^{2}\big{(}\mathbb{P}_{z^{\prime}}^{\pi}(\tau_{h})\hskip
1.42262pt\|\hskip 1.42262pt\mathbb{\widehat{P}}_{z}^{\pi}(\tau_{h})\big{)}\leq
1+\chi^{2}\big{(}\mathbb{P}_{z^{\prime}}^{\pi}(\tau_{h},s_{1:h})\hskip
1.42262pt\|\hskip
1.42262pt\mathbb{\widehat{P}}_{z}^{\pi}(\tau_{h},s_{1:h})\big{)}$
$\displaystyle\leq
1+\chi^{2}\left(\prod_{h^{\prime}=1}^{h}\mathbb{P}_{z^{\prime}}^{\pi}(g_{h},s_{h+1}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h},s_{h})\cdot\mathbb{O}(o_{h}\hskip
1.42262pt|\hskip 1.42262pts_{h})\hskip 1.42262pt\|\hskip
1.42262pt\prod_{h^{\prime}=1}^{h}\mathbb{P}_{z^{\prime}}^{\pi}(g_{h},s_{h+1}\hskip
1.42262pt|\hskip
1.42262pt\tau_{h},s_{h})\cdot\mathbb{O}_{\widehat{\gamma}}(o_{h}\hskip
1.42262pt|\hskip 1.42262pts_{h})\right)$
$\displaystyle\leq\big{(}1+\max_{s\in\mathcal{S}}\big{\\{}\chi^{2}\big{(}\mathbb{O}(\cdot\hskip
1.42262pt|\hskip 1.42262pts)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{O}_{\widehat{\gamma}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts)\big{)}\big{\\}}\big{)}^{H}\leq\left(1+\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}\right)^{H},$ (D.26)

where the first inequality follows data processing inequality and the second
inequality arises from the tensorization (Theorem 7.32 and §7.12, Polyanskiy
and Wu,, 2022). To ensure that
$L_{h,t}^{\mathtt{LLM}}(z^{\prime})\leq\beta_{h,t}^{\mathtt{LLM}}$ holds for
all $(z^{\prime},h,t)\in\mathcal{Z}\times[H]\times[T]$ with probability at
least $1-\delta$, we let

$\prod_{i\in[t]\backslash\mathcal{X}^{t}_{\mathtt{exp}}}\sqrt{1+\chi^{2}\big{(}\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\hskip
1.42262pt\|\hskip
1.42262pt\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}}\cdot\exp\left(-\frac{\beta_{h,t}^{\mathtt{LLM}}}{4}\right)=\frac{\delta}{|\mathcal{Z}|},$

with a union bound taken over $\mathcal{Z}$, since Lemma F.1 has ensured the
inequality holds for all $(h,t)\in[H]\times[T]$. Thus, the constant
$\beta_{h,t}^{\mathtt{LLM}}$ is then chosen as

$\displaystyle\beta_{h,t}^{\mathtt{LLM}}$
$\displaystyle=2\sum_{i\in[t]\backslash\mathcal{X}^{t}_{\mathtt{exp}}}\log\left(1+\chi^{2}\big{(}\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\hskip
1.42262pt\|\hskip
1.42262pt\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}\right)+4\log(|\mathcal{Z}|/\delta)$
$\displaystyle\leq\left(t-|\mathcal{X}^{t}_{\mathtt{exp}}|\right)\cdot
H\log\left(1+\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)^{2}\right)+4\log(|\mathcal{Z}|/\delta)$
$\displaystyle\leq\left(t-|\mathcal{X}^{t}_{\mathtt{exp}}|\right)\cdot
H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)^{2}+4\log(|\mathcal{Z}|/\delta),$

which is based on (D.25), (D.26) by taking a union bound over $\mathcal{Z}$,
and the last inequality results from $\log(1+x)\leq x$ for all $x\geq 0$.
Similarly, for the exploration episodes, we let

$\displaystyle\mathbb{\widehat{P}}_{z}$
$\displaystyle(L_{h,t}^{\mathtt{exp}}(z^{\prime})\geq\beta_{h,t}^{\mathtt{exp}})\leq\underset{\lambda\geq
0}{\inf}\
\mathbb{E}\left[\exp(\lambda\cdot(L_{h,t}^{\mathtt{exp}}-\beta_{h,t}^{\mathtt{exp}}))\right]$
$\displaystyle\quad\leq\prod_{i\in\mathcal{X}^{t}_{\mathtt{exp}}}\sqrt{1-D^{2}_{\rm
H}\big{(}\mathbb{P}^{\widehat{\pi}^{i}}_{z^{\prime}}(\breve{\tau}_{h/t}^{i}),\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}}\cdot\sqrt{1+\chi^{2}\big{(}\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\hskip
1.42262pt\|\hskip
1.42262pt\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}}\cdot\exp\left(-\frac{1}{4}\beta_{h,t}^{\mathtt{exp}}\right).$

Furthermore, based on Definition 4.4, the expolration episodes satisfies that

$\displaystyle\sum_{i\in\mathcal{X}^{t}_{\mathtt{exp}}}$ $\displaystyle
D^{2}_{\rm
H}\big{(}\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i}),\mathbb{P}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}\geq\sum_{i\in\mathcal{X}^{t-1}_{\mathtt{exp}}}D^{2}_{\rm
H}\big{(}\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\tau_{H}),\mathbb{P}_{z}^{\widehat{\pi}^{i}}(\tau_{H})\big{)}\geq{\eta}\cdot|\mathcal{X}^{t-1}_{\mathtt{exp}}|.$
(D.27)

To ensure that
$L_{h,t}^{\mathtt{exp}}(z^{\prime})\leq\beta_{h,t}^{\mathtt{exp}}$ holds for
all $(z^{\prime},h,t)\in\mathcal{Z}\times[H]\times[T]$ with high probability,
we take

$\prod_{i\in[t]\backslash\mathcal{X}^{t}_{\mathtt{exp}}}\sqrt{1-D^{2}_{\rm
H}\big{(}\mathbb{P}^{\widehat{\pi}^{i}}_{z^{\prime}}(\breve{\tau}_{h/t}^{i}),\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}}\cdot\sqrt{1+\chi^{2}\big{(}\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\hskip
1.42262pt\|\hskip
1.42262pt\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}}\cdot\exp\left(-\frac{\beta_{h,t}^{\mathtt{exp}}}{4}\right)=\frac{\delta}{|\mathcal{Z}|},$

with a union bound taken over $\mathcal{Z}$, and thus the constant
$\beta_{h,t}^{\mathtt{exp}}$ is chosen as

$\displaystyle\beta_{h,t}^{\mathtt{exp}}$
$\displaystyle=2\sum_{i\in\mathcal{X}^{t}_{\mathtt{exp}}}\log\left(1-D^{2}_{\rm
H}\left(\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i}),\mathbb{{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\right)\right)$
$\displaystyle\quad+2\sum_{i\in\mathcal{X}^{t}_{\mathtt{exp}}}\log\left(1+\chi^{2}\big{(}\mathbb{P}_{z^{\prime}}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\hskip
1.42262pt\|\hskip
1.42262pt\mathbb{\widehat{P}}_{z}^{\widehat{\pi}^{i}}(\breve{\tau}_{h/t}^{i})\big{)}\right)+4\log(|\mathcal{Z}|/\delta)$
$\displaystyle\leq|\mathcal{X}^{t}_{\mathtt{exp}}|\cdot
H\log\left(1+\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)^{2}\right)+4\log(|\mathcal{Z}|/\delta)-2\eta\cdot|\mathcal{X}^{t-1}_{\mathtt{exp}}|$
$\displaystyle\leq|\mathcal{X}^{t}_{\mathtt{exp}}|\cdot
H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)^{2}+4\log(|\mathcal{Z}|/\delta)-2\eta\cdot(|\mathcal{X}^{t}_{\mathtt{exp}}|-1),$

where the first inequality results from (D.26), (D.27) and facts that
$\log(1-x)\leq-x$ for all $x\leq 1$ and $\log(1+x)\leq x$ for all $x\geq 0$,
and then we complete the proof of Lemma D.1. $\Box$

###  D.4 Proof of Lemma D.2

######  Lemma D.2 (Learning Target of Contrastive Loss).

For any observation-state pair $(o,s)\in\mathcal{O}\times\mathcal{S}$ sampled
from the contrastive collection process, the learning target is
$f^{*}(o,s)={\mathbb{O}(o\hskip 1.42262pt|\hskip
1.42262pts)}/{\mathcal{P}^{-}(o)}.$

_Proof of Lemma D.2._ For any $(o,s)\in\mathcal{O}\times\mathcal{S}$, the
posterior probability of label $y$ follows that

$\displaystyle\mathbb{D}(y\hskip 1.42262pt|\hskip
1.42262pto,s):=\mathbb{P}_{\mathcal{C}}(y\hskip 1.42262pt|\hskip
1.42262pto,s)=\frac{\mathbb{P}_{\mathcal{C}}(o\hskip 1.42262pt|\hskip
1.42262pts,y)\cdot\mathbb{P}_{\mathcal{C}}(s\hskip 1.42262pt|\hskip
1.42262pty)}{\sum_{y\in\\{0,1\\}}\mathbb{P}_{\mathcal{C}}(o\hskip
1.42262pt|\hskip 1.42262pts,y)\cdot\mathbb{P}_{\mathcal{C}}(s\hskip
1.42262pt|\hskip 1.42262pty)},$

where the equation follows the Baye’s Theorem and
$\mathbb{P}_{\mathcal{C}}(y=0)=\mathbb{P}_{\mathcal{C}}(y=1)=1/2$. Moreover,
the contrastive data collection process in §3.2 indicates that

$\mathbb{P}_{\mathcal{C}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts,y=0)=\mathbb{O}(\cdot\hskip 1.42262pt|\hskip
1.42262pts),\quad\mathbb{P}_{\mathcal{C}}(\cdot\hskip 1.42262pt|\hskip
1.42262pts,y=1)=\mathcal{P}^{-}(\cdot),$ (D.28)

and data are labeled independent of data itself, such that
$\mathbb{P}_{\mathcal{C}}(s\hskip 1.42262pt|\hskip
1.42262pty)=\mathbb{P}_{\mathcal{C}}(s)$. Thus,
$\mathbb{P}_{\mathcal{C}}(y\hskip 1.42262pt|\hskip
1.42262pto,s)=\mathbb{P}_{\mathcal{C}}(o\hskip 1.42262pt|\hskip
1.42262pts,y)/(\mathcal{P}^{-}(o)+\mathbb{O}(o\hskip 1.42262pt|\hskip
1.42262pts))$. Recall that the population risk is

$\mathcal{R}_{\rm
CT}(\gamma;\mathcal{D}_{\mathtt{Rep}})=\mathbb{E}\left[D_{\rm
KL}\left(\mathbb{D}_{\gamma}(\cdot|o,s)\hskip 1.42262pt\|\hskip
1.42262pt\mathbb{D}(\cdot|o,s)\right)+\mathrm{Ent}(\mathbb{D}(\cdot|o,s))\right].$

As the minimum is attained at $\mathbb{D}_{\gamma}(\cdot\hskip
1.42262pt|\hskip 1.42262pto,s)=\mathbb{D}(\cdot\hskip 1.42262pt|\hskip
1.42262pto,s)$. Following (5.1), the learning target follows

$\frac{\mathbb{P}_{\mathcal{C}}(o\hskip 1.42262pt|\hskip
1.42262pts,y)}{\mathcal{P}^{-}(o)+\mathbb{O}(o\hskip 1.42262pt|\hskip
1.42262pts)}=\left(\frac{f^{*}(o,s)}{1+f^{*}(o,s)}\right)^{y}\left(\frac{1}{1+f^{*}(o,s)}\right)^{1-y}.$
(D.29)

By solving the equation in (D.29), the learning target follows that
$f^{*}(o,s)=\mathbb{O}(o\hskip 1.42262pt|\hskip
1.42262pts)/\mathcal{P}^{-}(o)$ for the contrastive loss in (3.8), and then we
conclude the proof of Lemma D.2. $\Box$

##  Appendix E Proof for Section B: Extentions

###  E.1 Proof of Proposition B.1

###### Proof of Proposition B.1.

Based on the law of total probability, it holds that

$\displaystyle\mathbb{P}_{\mathcal{D}}\left(o_{h}\hskip 1.42262pt|\hskip
1.42262pt(o,g)_{1:h-1},\mathcal{H}_{t}\right)$
$\displaystyle=\sum_{z\in\mathcal{Z}}\mathbb{P}_{z}\left(o_{h}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h-1}\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:h-1},\mathcal{H}_{t}\right)$ (E.1)

Furthermore, based on Baye’s theorem, we have

$\displaystyle\mathbb{P}_{\mathcal{D}}\left(z\hskip 1.42262pt|\hskip
1.42262pt(o,g)_{1:h-1},\mathcal{H}_{t}\right)=\frac{\prod_{h^{\prime}=1}^{h-2}\mathbb{P}_{z}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}}\right)}{\prod_{h^{\prime}=1}^{h-2}\mathbb{P}_{\mathcal{D}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)}\cdot\mathbb{P}_{\mathcal{D}}(z\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t}),$ (E.2)

Hence, (E.1) and (E.2) jointly indicates that

$\displaystyle\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{\mathcal{D}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)$
$\displaystyle=\mathbb{P}_{\mathcal{D}}\left(o_{h}\hskip 1.42262pt|\hskip
1.42262pt(o,g)_{1:h-1},\mathcal{H}_{t}\right)\cdot\prod_{h^{\prime}=1}^{h-2}\mathbb{P}_{\mathcal{D}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)$
$\displaystyle=\sum_{z\in\mathcal{Z}}\mathbb{P}_{z}\left(o_{h}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h-1}\right)\cdot\prod_{h^{\prime}=1}^{h-2}\mathbb{P}_{z}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}}\right)\cdot\mathbb{P}_{\mathcal{D}}(z\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t})$
$\displaystyle=\sum_{z\in\mathcal{Z}}\left(\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{z}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}}\right)\right)\cdot\mathbb{P}_{\mathcal{D}}(z\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t}).$ (E.3)

Following the definition of marginal distributions, it holds that

$\displaystyle\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{h}\hskip 1.42262pt|\hskip
1.42262pto_{1},\mathrm{\bf do}\hskip 1.70717ptg_{1:h-1}\right)$
$\displaystyle=\int_{o_{2:h-1}}\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{\mathcal{D}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right){\mathrm{d}}o_{2:h-1}$
$\displaystyle=\sum_{z\in\mathcal{Z}}\left(\int_{o_{2:h-1}}\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{z}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}}\right){\mathrm{d}}o_{2:h-1}\right)\cdot\mathbb{P}_{\mathcal{D}}(z\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t})$
$\displaystyle=\sum_{z\in\mathcal{Z}}\mathbb{P}_{z}\left(o_{h}\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right)\cdot\mathbb{P}_{\mathcal{D}}(z\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t}),$

where the second equation follows (E.3) and then we complete the proof of
Proposition B.1. ∎

###  E.2 Proof of Corollary B.3

#### Notations.

Denote $(\mathcal{J},\mathcal{\widehat{J}})$ and
$({\pi}_{z}^{*},\widehat{\pi}_{z}^{*})$, and
$(\mathbb{P}_{z,h},\mathbb{\widehat{P}}_{z,h})$ as the value functions,
optimal policies, and probability under the environment concerning the ground-
truth $\mathbb{O}$ and the pretrained $\mathbb{O}_{\widehat{\gamma}}$. Let
$(\mathcal{\widehat{J}}_{t,\mathtt{LLM}},\widehat{\pi}_{\mathtt{LLM}}^{t,*})$
be the value function of the environment simulated by pretrained
$\mathtt{LLM}_{\widehat{\theta}}$ and its optimal policy;
$\mathcal{J}_{t,\mathtt{LLM}}$ denote the value function of the environment
simulated by perfect $\mathtt{LLM}$;
$(\mathbb{P}_{\mathtt{LLM}}^{t},\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t})$ are
the probability under environment simulated by perfect $\mathtt{LLM}$ or
pretrained $\mathtt{LLM}_{\widehat{\theta}}$.

###### Proof of Corollary B.3.

Condition on the event $\mathcal{E}_{1}$ that both Theorem 2 and 5.5 hold, the
regret under the practical setting can be decomposed as

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle\leq\underbrace{\sum_{t=1}^{T}\mathcal{\widehat{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})}_{\textbf{(i})}+\underbrace{\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}_{z}^{*},\omega^{t})\right]}_{\textbf{(ii})}$
$\displaystyle\quad+\underbrace{\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}^{t},\omega^{t})\right]}_{\textbf{(iii})}$
$\displaystyle\quad+\underbrace{\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}^{t},\omega^{t})-\mathcal{J}_{z}(\widehat{\pi}^{t},\omega^{t})\right]}_{\textbf{(iv})}+\underbrace{\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{J}_{z}(\widehat{\pi}^{t},\omega^{t})-\mathcal{\widehat{J}}_{z}(\widehat{\pi}^{t},\omega^{t})\right]}_{\textbf{(v})}.$
(E.4)

Step 1. Bound (i) and (v) with Translator’s Pretraining Error.
Similar to (D.11) in the proof of Theorem 5.7, it holds that

$\displaystyle\textbf{\small(i})+\textbf{\small(vi})\leq
2H^{2}T\lambda_{R}^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta),$ (E.5)

following the pretraining error in Theorem 5.5.
Step 2. Bound (iii) via Optimality in Planner’s Algorithm.
Recall that Planner conducts task planning via the mixture policy:

$\pi_{h}^{t}(\cdot\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})\sim(1-\epsilon)\cdot\widehat{\pi}_{h,\mathtt{LLM}}^{t,*}(\cdot\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})+\epsilon\cdot\pi_{h,\mathtt{exp}}(\cdot|\tau_{h}^{t}),$
(E.6)

Following this, it holds that

$\displaystyle\textbf{\small(iii})$
$\displaystyle=\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}_{\mathtt{LLM}}^{t,*},\omega^{t})\right]+\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}_{\mathtt{LLM}}^{t,*},\omega^{t})-\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}^{t},\omega^{t})\right]$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}_{\mathtt{LLM}}^{t,*},\omega^{t})-(1-\epsilon)\cdot\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}_{\mathtt{LLM}}^{t,*},\omega^{t})-\epsilon\cdot\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\pi_{\mathtt{exp}},\omega^{t})\right]\leq
2HT\epsilon,$ (E.7)

where the the first inequality results from the optimality of
$\widehat{\pi}_{\mathtt{LLM}}^{t,*}$ under simulated environment.
Step 3. Bound (ii) and (iv) with LLM’s Pretraining Error.
For any policy $\pi\in\Pi$, given history $\mathcal{H}_{t}$, the performance
difference follows

$\displaystyle\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\pi,\omega^{t})-\mathcal{J}_{z}(\pi,\omega^{t})$
$\displaystyle=\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\pi,\omega^{t})-\mathcal{J}_{t,\mathtt{LLM}}(\pi,\omega^{t})+\mathcal{J}_{t,\mathtt{LLM}}(\pi,\omega^{t})-\mathcal{J}_{z}(\pi,\omega^{t})$
$\displaystyle\leq\underbrace{\mathbb{E}\left[\sum_{h=1}^{H}\int_{o_{h}}\left(\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}\left(o_{h}\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right)-\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{h}\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right)\right){\mathrm{d}}o_{h}\right]}_{\textbf{(vi})}$
$\displaystyle\quad+\underbrace{\sup_{g_{1:H-1}}\sum_{h=1}^{H}\int_{o_{h}}\left(\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{h}\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right)-\mathbb{P}_{z}\left(o_{h}\hskip 1.42262pt|\hskip
1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right)\right){\mathrm{d}}o_{h}}_{\textbf{(vii})},$

where the inequality arises from $\|r_{h}\|_{\infty}\leq 1$ depending solely
on $o_{h}$. Furthermore, we have

$\displaystyle\int_{o_{h}}\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}\left(o_{h}\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right)-\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{h}\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right){\mathrm{d}}o_{h}$
$\displaystyle\quad=\int_{o_{2:h}}\left(\prod_{h^{\prime}=1}^{h-1}\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}}\right)-\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}}\right)\right){\mathrm{d}}o_{2:h}.$ (E.8)

Following the arguments above, the difference can be decomposed as

$\displaystyle\prod_{h^{\prime}=1}^{h-1}\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}}\right)-\prod_{h^{\prime}=1}^{h-1}\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}}\right)$
$\displaystyle\quad=\sum_{h^{\prime}=1}^{h-1}\left(\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}}\right)-\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}}\right)\right)$
$\displaystyle\qquad\cdot\prod_{k=h^{\prime}+1}^{h-1}\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}\left(o_{k+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:k}\right)\cdot\prod_{k=1}^{h^{\prime}-1}\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{k+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:k}\right)$
$\displaystyle\quad=\sum_{h^{\prime}=1}^{h-1}\left(\mathtt{LLM}_{\widehat{\theta}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)-\mathtt{LLM}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)\right)$
$\displaystyle\qquad\cdot\prod_{k=h^{\prime}+1}^{h-1}\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}\left(o_{k+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:k}\right)\cdot\prod_{k=1}^{h^{\prime}-1}\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{k+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:k}\right).$ (E.9)

Combine (E.8) and (E.9), it holds that

$\displaystyle\textbf{(vi})$
$\displaystyle\leq\sum_{h=1}^{H}\int_{o_{2:h}}\sum_{h^{\prime}=1}^{h-1}\left(\mathtt{LLM}_{\widehat{\theta}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)-\mathtt{LLM}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)\right)$
$\displaystyle\qquad\cdot\prod_{k=h^{\prime}+1}^{h-1}\widehat{\mathbb{P}}_{\mathtt{LLM}}^{t}\left(o_{k+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:k}\right)\cdot\prod_{k=1}^{h^{\prime}-1}\mathbb{P}_{\mathtt{LLM}}^{t}\left(o_{k+1}\hskip
1.42262pt|\hskip 1.42262pt(o,g)_{1:k}\right){\mathrm{d}}o_{2:h}$
$\displaystyle\leq\sum_{h=1}^{H}\sum_{h^{\prime}=1}^{h-1}\mathbb{E}_{o_{1:h^{\prime}}|\mathcal{H}_{t}}\left[D_{\rm
TV}\left(\mathtt{LLM}_{\widehat{\theta}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right),\mathtt{LLM}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)\right)\right].$ (E.10)

Following (E.10), for any policy $\pi\in\Pi$, we have

$\displaystyle\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\pi,\omega^{t})-\mathcal{J}_{t,\mathtt{LLM}}(\pi,\omega^{t})\right]$
$\displaystyle\quad\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\sum_{h^{\prime}=1}^{h-1}\mathbb{E}_{\mathcal{H}_{t}}\mathbb{E}_{(o,g)_{1:h^{\prime}}|\mathcal{H}_{t}}\left[D_{\rm
TV}\left(\mathtt{LLM}_{\widehat{\theta}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right),\mathtt{LLM}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)\right)\right]$
$\displaystyle\quad\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\sum_{h^{\prime}=1}^{h-1}\lambda_{S,1}\lambda_{S,2}^{-1}\cdot\bar{\mathbb{E}}_{\mathcal{D}_{\mathtt{LLM}}}\left[D_{\rm
TV}\left(\mathtt{LLM}_{\widehat{\theta}}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right),\mathtt{LLM}\left(o_{h^{\prime}+1}\hskip
1.42262pt|\hskip
1.42262pt(o,g)_{1:h^{\prime}},\mathcal{H}_{t}\right)\right)\right]$
$\displaystyle\quad\leq
H^{2}T\lambda_{S,1}\lambda_{S,2}^{-1}\cdot\Delta_{\mathtt{LLM}}(N_{\rm
p},T_{\rm p},H,\delta)$ (E.11)

where the first inequality follows Theorem 2 and Assumption B.2. Based on
Proposition B.1, the term (vii) can be upper bounded using the Bayesian
aggregated arguments such that

$\displaystyle\textbf{(vii})$
$\displaystyle=\sup_{g_{1:H-1}}\sum_{z^{\prime}\neq
z}\sum_{h=1}^{H}\int_{o_{h}}(\mathbb{P}_{z^{\prime}}\left(o_{h}\hskip
1.42262pt|\hskip 1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right)-\mathbb{P}_{z}\left(o_{h}\hskip 1.42262pt|\hskip
1.42262pto_{1},\mathrm{\bf do}\hskip
1.70717ptg_{1:h-1}\right))\cdot\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t}){\mathrm{d}}o_{h}\leq
H\sum_{z^{\prime}\neq z}\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t}).$

Following the arguments above, for any policy $\pi\in\Pi$, it holds that

$\displaystyle\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\pi,\omega^{t})-\mathcal{J}_{z}(\pi,\omega^{t})\right]\leq
H\sum_{t=1}^{T}\sum_{z^{\prime}\neq
z}\mathbb{E}_{\mathcal{H}_{t}}\left[\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathcal{H}_{t})\right],$ (E.12)

Combine (E.11), (E.12) and the similar concentration arguments of posterior
probability in (D.20), denoted by event $\mathcal{E}_{2}$ (see proof of
Theorem 5.7 in §D.2), it holds that

$\displaystyle\textbf{(ii)}+\textbf{(iv)}$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\left(\mathcal{{J}}_{z}(\widehat{\pi}_{z}^{*},\omega^{t})-\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}_{z}^{*},\omega^{t})\right)\cdot\operatorname{\mathds{1}}\left(\mathcal{E}_{2}\text{~{}holds}\right)\right]$
$\displaystyle\quad+\sum_{t=1}^{T}\mathbb{E}_{\mathcal{H}_{t}}\left[\left(\mathcal{\widehat{J}}_{t,\mathtt{LLM}}(\widehat{\pi}^{t},\omega^{t})-\mathcal{J}_{z}(\widehat{\pi}^{t},\omega^{t})\right)\cdot\operatorname{\mathds{1}}\left(\mathcal{E}_{2}\text{~{}holds}\right)\right]+2HT\delta$
$\displaystyle\leq
2H^{2}T\lambda_{S,1}\lambda_{S,2}^{-1}\cdot\Delta_{\mathtt{LLM}}(N_{\rm
p},T_{\rm p},H,\delta)+2HT\delta$ $\displaystyle\qquad+c_{0}\cdot
2H\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)\cdot\left(\eta\epsilon-H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}\right)^{-1}$ (E.13)

Step 4. Conclude the Proof based on Step 1, Step 2, and Step 3.
Combine (E.5), (E.7) and (E.13), we have

$\displaystyle{\rm Reg}_{z}(T)$ $\displaystyle\leq\underbrace{c_{0}\cdot
2H\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)\cdot\left(\eta\epsilon-H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}\right)^{-1}}_{\textbf{(viii})}+4HT\delta$
$\displaystyle\qquad+\underbrace{2HT\eta^{-1}\left(\eta\epsilon-H\lambda^{-1}_{R}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm
p},H,\delta)^{2}\right)}_{\textbf{(ix})}+2H^{2}T\lambda_{S,1}\lambda_{S,2}^{-1}\cdot\Delta_{\mathtt{LLM}}(N_{\rm
p},T_{\rm p},H,\delta)$
$\displaystyle\qquad+2H^{2}T(\eta\lambda_{R})^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm
p},H,\delta)^{2}+2H^{2}T\lambda_{R}^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)$
$\displaystyle\leq\mathcal{O}\Big{(}H\sqrt{\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)\cdot
T/\eta}+H^{2}T\cdot\Delta_{\rm p,wm}(N_{\rm p},T_{\rm
p},H,\delta,\xi)\Big{)}+4HT\delta,$ (E.14)

if we choose
$\epsilon=(\log(c_{\mathcal{Z}}|\mathcal{Z}|\sqrt{T})/T\eta)^{1/2}+H(\eta\lambda_{\min})^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}$ to strike an exploration-exploitation balance
between (viii) and (ix). Thus, the cumulative pretraining error follows

$\displaystyle\Delta_{\rm p,wm}$ $\displaystyle(N_{\rm p},T_{\rm
p},H,\delta,\xi)=2(\eta\lambda_{R})^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm
p},T_{\rm p},H,\delta)^{2}$
$\displaystyle+2\lambda_{R}^{-1}\cdot\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm
p},H,\delta)+2\lambda_{S,1}\lambda_{S,2}^{-1}\cdot\Delta_{\mathtt{LLM}}(N_{\rm
p},T_{\rm p},H,\delta).$

Here, $\xi=(\eta,\lambda_{S,1},\lambda_{S,2},\lambda_{R})$ denotes the set of
distinguishability and coverage coefficients in Definition 4.4 and Assumption
5.6, and $\Delta_{\mathtt{LLM}}(N_{\rm p},T_{\rm p},H,\delta)$ and
$\Delta_{\mathtt{Rep}}(N_{\rm p},T_{\rm p},H,\delta)$ are pretraining errors
defined in Theorem 2 and Theorem 5.5. By taking $\delta=1/\sqrt{T}$, we
complete the entire proof. ∎

###  E.3 Proof of Corollary B.4

The proof is similar to that in §C.2.
_Proof Sketch of Corollary B.4._ We first verify the claim in (B.2), which is
akin to Proposition 4.2. Note that for all $(h,t)\in[H]\times[T]$, based on
the law of total probability, it holds that

$\displaystyle\pi_{h,\mathtt{LLM}}^{t}\big{(}\mathbf{g}_{h}^{t}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h}^{t},\omega^{t}\big{)}$
$\displaystyle=\prod_{k\in\mathcal{K}}\mathtt{LLM}\big{(}g_{h,k}^{t}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h,k}^{t}\big{)}$
$\displaystyle=\prod_{k\in\mathcal{K}}\left(\sum_{z\in\mathcal{Z}}\mathbb{P}\left(g_{h,k}^{t}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h,k}^{t},z\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h,k}^{t}\right)\right)$
$\displaystyle=\prod_{k\in\mathcal{K}}\left(\sum_{z\in\mathcal{Z}}\pi^{*}_{z,h,k}\left(g_{h,k}^{t}\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t}\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t}\right)\right),$ (E.15)

where the first equation arises from the autoregressive manner of LLM, and the
last equation follows the generating distribution. The Planner takes a mixture
policy of $\pi_{\mathtt{exp}}$ and $\pi_{\mathtt{LLM}}$ such that

$\pi_{h}^{t}(\mathbf{g}_{h}^{t}\hskip 1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})\sim(1-\epsilon)\cdot\pi_{h,\mathtt{LLM}}^{t}(\mathbf{g}_{h}^{t}\hskip
1.42262pt|\hskip
1.42262pt\tau_{h}^{t},\omega^{t})+\epsilon\cdot\pi_{h,\mathtt{exp}}(\mathbf{g}_{h}^{t}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h}^{t}),$ (E.16)

for any $(h,t)\in[H]\times[T]$ given an $\eta$-distinguishable policy
$\pi_{\mathtt{exp}}$ (see Definition 4.4). Given a sequence of high-level
tasks $\\{\omega^{t}\\}_{t\in[T]}$, the regret can be decomposed as

$\displaystyle\text{Reg}(T)$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]+HT\epsilon,$
(E.17)

Recall that (C.3) indicates that for all $(h,t)\in[H]\times[T]$, we have

$\displaystyle\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)(\mathbf{g}_{h}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h},\omega)$
$\displaystyle\quad=\prod_{k\in\mathcal{K}}\left(\sum_{z^{\prime}\in\mathcal{Z}}\pi^{*}_{z^{\prime},h,k}\left(g_{h,k}\hskip
1.42262pt|\hskip
1.42262pt\tau_{h},\omega\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t}\right)\right)-\prod_{k\in\mathcal{K}}\pi_{z,h,k}^{*}(g_{h,k}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h},\omega)$ $\displaystyle\quad\leq
H\sum_{k\in\mathcal{K}}\left(\sum_{z^{\prime}\neq
z}(\pi^{*}_{z^{\prime},h,k}-\pi^{*}_{z,h,k})\left(g_{h,k}\hskip
1.42262pt|\hskip
1.42262pt\tau_{h},\omega\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z^{\prime}\hskip
1.42262pt|\hskip 1.42262pt\mathtt{pt}_{h}^{t}\right)\right)$
$\displaystyle\quad\qquad\cdot\prod_{k^{\prime}=1}^{k-1}\left(\sum_{z^{\prime\prime}\in\mathcal{Z}}\pi^{*}_{z^{\prime\prime},h,k^{\prime}}\left(g_{h,k,k^{\prime}}\hskip
1.42262pt|\hskip
1.42262pt\tau_{h},\omega\right)\cdot\mathbb{P}_{\mathcal{D}}\left(z^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t}\right)\right)\cdot\prod_{k^{\prime}=k+1}^{K}\pi_{z,h}^{*}(g_{h,k}\hskip
1.42262pt|\hskip 1.42262pt\tau_{h},\omega).$

Following this, we have

$\displaystyle\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h}^{t},\tau_{h}^{t},\omega^{t})$
$\displaystyle\leq HK\cdot\sum_{z^{\prime}\neq
z}\mathbb{P}_{\mathcal{D}}\left(z\hskip 1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t}\right),$ (E.18)

for all $(h,t)\in[H]\times[T]$. Based on Lemma C.1 and the similar arguments
in the proof Theorem 4.6 in §C.2, with probability at least $1-\delta$, the
following event $\mathcal{E}_{1}$ holds: for all $(h,t)\in[H]\times[T]$,

$\sum_{z^{\prime}\neq z}\mathbb{P}_{\mathcal{D}}(z^{\prime}\hskip
1.42262pt|\hskip
1.42262pt\mathtt{pt}_{h}^{t})\leq\mathcal{O}\left(\min\left\\{\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right)\eta^{-1}/|\mathcal{X}^{t-1}_{\mathtt{exp}}|,1\right\\}\right),$
(E.19)

where
$\mathcal{X}^{t}_{\mathtt{exp}}=\\{i\in[t]:\pi^{i}=\pi_{\mathtt{exp}}\\}$
denotes the set of exploration episodes. Based on (E.15), (E.18) and
conditioned on $\mathcal{E}_{1}$, it holds that

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h}^{t},\tau_{h}^{t},\omega^{t})\right]$
$\displaystyle\leq
2\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)HK\eta^{-1}\cdot\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{\tau_{h}^{t}\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\min\left\\{1/|\mathcal{X}^{t-1}_{\mathtt{exp}}|,1\right\\}\right],$
(E.20)

Note that $\mathds{1}(\pi^{t}=\pi_{\mathtt{exp}})\overset{\rm
iid}{\sim}\text{Bernuolli}(\epsilon)$ for all $t\in[T]$. Besides, with
probability at least $1-\delta$, the following event $\mathcal{E}_{2}$ holds:

$\displaystyle\sum_{t=1}^{T}\min\left\\{1/|\mathcal{X}^{t-1}_{\mathtt{exp}}|,1\right\\}\leq\mathcal{O}(\epsilon^{-1}\log(T\log
T/\delta)).$ (E.21)

based on Lemma F.5. Combine (E.17), (E.20) and (E.21), it follows that

$\displaystyle{\rm Reg}_{z}(T)$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h},\tau_{h},\omega^{t})\operatorname{\mathds{1}}\left(\mathcal{E}_{1}\cap\mathcal{E}_{2}\text{~{}holds}\right)\right]$
$\displaystyle\quad+\sum_{t=1}^{T}\sum_{h=1}^{H}\mathbb{E}_{\mathcal{H}_{t}\sim\bigotimes_{i=1}^{t-1}\mathbb{P}_{z}^{\pi_{i}}}\mathbb{E}_{(s_{h}^{t},\tau_{h}^{t})\sim\mathbb{P}_{z}^{\pi^{t}}}\left[\left(\pi_{z,h}^{*}-{\pi^{t}_{h,\mathtt{LLM}}}\right)Q_{z,h}^{*}(s_{h},\tau_{h},\omega^{t})\operatorname{\mathds{1}}\left(\mathcal{E}_{1}\cap\mathcal{E}_{2}\text{~{}fails}\right)\right]+HT\epsilon$
$\displaystyle\leq\mathcal{O}\Big{(}\log(c_{\mathcal{Z}}|\mathcal{Z}|/\delta)H^{2}K\log(T\log
T/\delta)\cdot(\eta\epsilon)^{-1}+HT\epsilon+H\sqrt{T}\log(1/\delta)+2HT\delta\Big{)}$
$\displaystyle\leq\tilde{\mathcal{O}}\left(H^{\frac{3}{2}}\sqrt{TK/\eta\cdot\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right)}\right),$

where we choose to expolre with probability
$\epsilon=(HK\log\left(c_{\mathcal{Z}}|\mathcal{Z}|/\delta\right)/T\eta)^{1/2}$
in the last inequality. If we take $\delta=1/\sqrt{T}$ in the arguments above,
then we conclude the proof of Corollary B.4. $\Box$

##  Appendix F Technical Lemmas

######  Lemma F.1 (Martingale Concentration Inequality).

Let $X_{1},\dots,X_{T}$ be a sequence of real-valued random variables adapted
to a filter $(\mathscr{F}_{t})_{t\leq T}$. For any $\delta\in(0,1)$ and
$\lambda>0$, it holds that

$\mathbb{P}\left(\exists
T^{\prime}\in[T]:-\sum_{t=1}^{T^{\prime}}X_{t}\geq\sum_{t=1}^{T^{\prime}}\frac{1}{\lambda}\log\mathbb{E}\left[\exp(-\lambda
X_{t})|\mathscr{F}_{t-1}\right]+\frac{1}{\lambda}\log\left(1/\delta\right)\right)\leq\delta.$

_Proof of Lemma F.1_. See Lemma A.4 in Foster et al., (2021) and Theorem 13.2
in Zhang, (2023) for detailed proof. Lemma A.4 in Foster et al., (2021) is a
special case by taking $\lambda=1$.

######  Lemma F.2 (Donsker-Varadhan).

Let $P$ and $Q$ be the probability measures over $\mathcal{X}$, then

$D_{\rm KL}(P\hskip 1.42262pt\|\hskip
1.42262ptQ)=\underset{f\in\mathcal{F}}{\sup}\left\\{\mathbb{E}_{x\sim
P}\left[f(x)\right]-\log\mathbb{E}_{x\sim Q}\left[\exp(f(x))\right]\right\\},$

where $\mathcal{F}=\\{f:\mathcal{X}\mapsto\mathbb{R}\hskip 1.42262pt|\hskip
1.42262pt\mathbb{E}_{x\sim Q}\left[\exp(f(x))\right]\leq\infty\\}$.

_Proof of Lemma F.2_. See Donsker and Varadhan, (1976) for detailed proof.

######  Lemma F.3 (MLE guarantee).

Let $\mathcal{F}$ be finite function class and there exists
$f^{*}\in\mathcal{F}$ such that $f^{*}(x,y)=\mathbb{P}(y\hskip
1.42262pt|\hskip 1.42262ptx)$, where $\mathbb{P}(y\hskip 1.42262pt|\hskip
1.42262ptx)$ is the conditional distribution for estimation. Given a dataset
$\mathcal{D}=\\{x_{i},y_{i}\\}_{i\in[N]}$ where
$x_{i}\sim\mathbb{P}_{\mathcal{D}}(\cdot\hskip 1.42262pt|\hskip
1.42262ptx_{1:i-1},y_{1:i-1})$ and
$y_{i}\sim\mathbb{P}_{\mathcal{D}}(\cdot\hskip 1.42262pt|\hskip
1.42262ptx_{i})$ for all $i\in[N]$, we have

$\bar{\mathbb{E}}_{\mathcal{D}}\left[D_{\rm
TV}^{2}\left(\widehat{f}(x,\cdot),f^{*}(x,\cdot)\right)\right]\leq
2\log(N|\mathcal{F}|/\delta)/N$

with propbability at least $1-\delta$, where $\widehat{f}$ is the maximum
likelihood estimator such that

$\widehat{f}:=\underset{f\in\mathcal{F}}{\rm argmax}\
\mathbb{\widehat{E}}_{\mathcal{D}}\left[\log f(x,y)\right].$

_Proof of Lemma F.3_. See Theorem 21 in Agarwal et al., (2020) for detailed
proof.

######  Lemma F.4 (Performance Difference Lemma for POMDP).

Consider policies $\pi,\pi^{\prime}\in\Pi$, it holds

$\mathcal{J}(\pi)-\mathcal{J}(\pi^{\prime})=\sum_{h=1}^{H}\mathbb{E}_{\pi}\left[Q_{h}^{\pi^{\prime}}(s_{h},\tau_{h},g_{h})-V_{h}^{\pi^{\prime}}(s_{h},\tau_{h})\right].$

For fixed policy $\pi\in\Pi$ under different POMDPs, denoted by $\mathcal{M}$
and $\mathcal{M}^{\prime}$, then it holds that

$\mathcal{J}_{\mathcal{M}}(\pi)-\mathcal{J}_{\mathcal{M^{\prime}}}(\pi)=\sum_{h=1}^{H}\mathbb{E}_{\mathcal{M}}^{\pi}\left[(\mathbb{P}_{h,\mathcal{M}}V_{h+1,\mathcal{M}^{\prime}}^{\pi}-\mathbb{P}_{h,\mathcal{M}^{\prime}}V_{h+1,\mathcal{M}^{\prime}}^{\pi})(s_{h},\tau_{h},g_{h})\right],$

where
$\mathbb{P}_{h,\mathcal{M}}V_{h+1,\mathcal{M}^{\prime}}^{\pi}(s_{h},\tau_{h},g_{h})=\langle
V_{h+1,\mathcal{M}^{\prime}}^{\pi}(\cdot,\cdot),\mathbb{P}_{h,\mathcal{M}}(\cdot,\cdot\hskip
1.42262pt|\hskip
1.42262pts_{h},\tau_{h},g_{h})\rangle_{{\mathcal{S}}\times{\mathcal{T}}^{*}}$.

######  Lemma F.5.

Let $X_{t}\overset{\rm iid}{\sim}\text{Bernuolli}(\rho)$ and
$Y_{t}=\sum_{\tau=1}^{t}X_{\tau}$. For any $\delta\in(0,1)$ and $\rho>0$, with
probability greater than $1-\delta$, it holds that
$\sum_{t=1}^{T}\min\left\\{1/Y_{t},1\right\\}\leq\mathcal{O}(\rho^{-1}\log(T\log
T/\delta))$.

###### Proof of Lemma F.5.

Note that $\\{Y_{t}\\}_{t\in[T]}$ is non-decreasing and it holds that

$\sum_{t=1}^{T}\min\left\\{\frac{1}{Y_{t}},1\right\\}=\\#\\{t\in[T]:Y_{t}=0\\}+\sum_{t\in[T]:Y_{t}>0}\frac{1}{Y_{t}},$
(F.1)

and with probability at least $1-\delta$, the following event
$\mathcal{E}_{0}$ holds:

$t_{0}:=\\#\\{t\in[T]:Y_{t}=0\\}\leq\frac{\log(\delta)}{\log(1-\rho)}\leq\rho^{-1}\log(1/\delta),$

where the first inequality results from the property of Bernuolli random
variable, and the second inequality uses fact that $\log(1-x)\leq-x$ for all
$x\leq 1$. For notational simplicy, we write
$\\{t\in[T]:Y_{t}>0\\}=\\{t_{0},\dots,t_{0}+2^{N_{T}}-1\\}$. With probability
at least $1-\delta$, the following event $\mathcal{E}_{n}$ holds:

$Y_{t_{0}+2^{n}}=\sum_{\tau=1}^{t_{0}+2^{n}}X_{t}=\sum_{\tau=t_{0}+1}^{t_{0}+2^{n}}X_{t}\geq
2^{n}\rho-\sqrt{2^{n-1}\log(1/\delta)}.$ (F.2)

based on the Hoeffding inequality. Suppose that
$\\{\mathcal{E}_{n}\\}_{n\in[N_{T}]}$ holds, then we have

$\displaystyle\sum_{t\in[T]:Y_{t}>0}\frac{1}{Y_{t}}=\sum_{n=0}^{N_{T}}\sum_{t=t_{0}+2^{n}}^{2^{n+1}-1}\frac{1}{Y_{t}}\leq\sum_{n=0}^{N_{T}}\frac{2^{n}}{Y_{t_{0}+2^{n}}}\leq\sum_{n=0}^{N_{T}}\frac{2^{n}}{\max\\{2^{n}\rho-\sqrt{2^{n-1}\log(1/\delta)},1\\}}.$
(F.3)

Let $n_{0}=1+\lceil\log_{2}(\rho^{-2}\log(1/\delta))\rceil$ such that
$\rho-\sqrt{\log(1/\delta)/2^{n+1}}\geq\rho/2$. Following (F.3), it holds

$\displaystyle\sum_{t\in[T]:Y_{t}>0}\frac{1}{Y_{t}}\leq\sum_{n=0}^{n_{0}}2^{n}+\sum_{n=n_{0}+1}^{N_{T}}2\rho^{-1}\leq
2^{n_{0}+1}+2\rho^{-1}N_{T}\leq 8\rho^{-2}\log(1/\delta)+4\rho^{-1}\log T.$
(F.4)

Combine (F.2) and (F.4), by taking a union bound over
$\mathcal{E}_{0},\dots,\mathcal{E}_{N_{T}}$, then we can get

$\displaystyle\sum_{t=1}^{T}\min\left\\{\frac{1}{Y_{t}},1\right\\}$
$\displaystyle\leq
8\rho^{-2}\log(2N_{T}/\delta)+4\rho^{-1}\log(2TN_{T}/\delta)$
$\displaystyle\leq 8\rho^{-2}\log(4\log T/\delta)+4\rho^{-1}\log(4T\log
T/\delta)\leq\mathcal{O}(\rho^{-1}\log(T\log T/\delta)),$

where we use the fact that $\log_{2}T\leq 2\log T$, and then we finish the
proof of Lemma F.5. ∎

  *[HMDP]: Hierarchical Markov Decision Process
  *[POMDP]: Partially Observable Markov Decision Process
  *[MDP]: Markov Decision Process
  *[BAIL]: Bayesian aggregated imitation learning