MDP Sample Complexity Bounds — NeurIPS Poster
A NeurIPS conference poster detailing theoretical bounds on sample complexity for Markov Decision Processes, featuring sections on key takeaways, main results with complexity tables, algorithm descriptions, and proof sketches with state diagrams.
Paper context
Paper title: Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs Abstract: A NeurIPS conference poster detailing theoretical bounds on sample complexity for Markov Decision Processes, featuring sections on key takeaways, main results with complexity tables, algorithm descriptions, and proof sketches with state diagrams. Paper body (method & results): <!DOCTYPE html> <html lang="en"> <head> <meta content="text/html; charset=utf-8" http-equiv="content-type"/> <title>Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs</title> <!--Generated on Sun Mar 17 22:35:27 2024 by LaTeXML (version 0.8.7) http://dlmf.nist.gov/LaTeXML/.--> <meta content="width=device-width, initial-scale=1, shrink-to-fit=no" name="viewport"/> <link href="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0/dist/css/bootstrap.min.css" rel="stylesheet" type="text/css"/> <link href="/static/browse/0.3.4/css/ar5iv_0.7.4.min.css" rel="stylesheet" type="text/css"/> <link href="/static/browse/0.3.4/css/latexml_styles.css" rel="stylesheet" type="text/css"/> <script src="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0/dist/js/bootstrap.bundle.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/html2canvas/1.3.3/html2canvas.min.js"></script> <script src="/static/browse/0.3.4/js/addons.js"></script> <script src="/static/browse/0.3.4/js/feedbackOverlay.js"></script> <base href="/html/2403.11477v1/"/></head> <body> <nav class="ltx_page_navbar"> <nav class="ltx_TOC"> <ol class="ltx_toclist"> <li class="ltx_tocentry ltx_tocentry_section"> <a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S1" title="1 Introduction ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1 </span>Introduction</span></a> <ol class="ltx_toclist ltx_toclist_section"> <li class="ltx_tocentry ltx_tocentry_subsection"> <a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S1.SS1" title="1.1 Related Work ‣ 1 Introduction ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1.1 </span>Related Work</span></a> <ol class="ltx_toclist ltx_toclist_subsection"> <li class="ltx_tocentry ltx_tocentry_subsubsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S1.SS1.SSS1" title="1.1.1 Average-reward MDPs ‣ 1.1 Related Work ‣ 1 Introduction ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1.1.1 </span>Average-reward MDPs</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsubsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S1.SS1.SSS2" title="1.1.2 Discounted MDPs ‣ 1.1 Related Work ‣ 1 Introduction ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1.1.2 </span>Discounted MDPs</span></a></li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S1.SS2" title="1.2 Our Approach ‣ 1 Introduction ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1.2 </span>Our Approach</span></a></li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_section"> <a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S2" title="2 Problem Setup and Preliminaries ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">2 </span>Problem Setup and Preliminaries</span></a> <ol class="ltx_toclist ltx_toclist_section"> <li class="ltx_tocentry ltx_tocentry_paragraph"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S2.SS0.SSS0.Px1" title="Average-reward criterion ‣ 2 Problem Setup and Preliminaries ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title">Average-reward criterion</span></a></li> <li class="ltx_tocentry ltx_tocentry_paragraph"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S2.SS0.SSS0.Px2" title="Complexity parameters ‣ 2 Problem Setup and Preliminaries ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title">Complexity parameters</span></a></li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_section"> <a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S3" title="3 Main Results ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">3 </span>Main Results</span></a> <ol class="ltx_toclist ltx_toclist_section"> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S3.SS1" title="3.1 Weakly Communicating MDPs ‣ 3 Main Results ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">3.1 </span>Weakly Communicating MDPs</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S3.SS2" title="3.2 General MDPs ‣ 3 Main Results ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">3.2 </span>General MDPs</span></a></li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_section"> <a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S4" title="4 Outline of Analysis ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">4 </span>Outline of Analysis</span></a> <ol class="ltx_toclist ltx_toclist_section"> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S4.SS1" title="4.1 Weakly Communicating MDPs ‣ 4 Outline of Analysis ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">4.1 </span>Weakly Communicating MDPs</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S4.SS2" title="4.2 General MDPs ‣ 4 Outline of Analysis ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">4.2 </span>General MDPs</span></a></li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_section"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#S5" title="5 Conclusion ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">5 </span>Conclusion</span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"> <a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#A1" title="Appendix A Proofs for Weakly Communicating MDPs ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">A </span>Proofs for Weakly Communicating MDPs</span></a> <ol class="ltx_toclist ltx_toclist_appendix"> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#A1.SS1" title="A.1 Technical Lemmas ‣ Appendix A Proofs for Weakly Communicating MDPs ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">A.1 </span>Technical Lemmas</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#A1.SS2" title="A.2 Proofs of Theorem 1 and 2 ‣ Appendix A Proofs for Weakly Communicating MDPs ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">A.2 </span>Proofs of Theorem <span class="ltx_text ltx_ref_tag">1</span> and <span class="ltx_text ltx_ref_tag">2</span></span></a></li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_appendix"> <a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#A2" title="Appendix B Proofs for General MDPs ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">B </span>Proofs for General MDPs</span></a> <ol class="ltx_toclist ltx_toclist_appendix"> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#A2.SS1" title="B.1 Proof of Theorem 5 ‣ Appendix B Proofs for General MDPs ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">B.1 </span>Proof of Theorem <span class="ltx_text ltx_ref_tag">5</span></span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#A2.SS2" title="B.2 Proof of Theorem 6 (Discounted MDP Bounds) ‣ Appendix B Proofs for General MDPs ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">B.2 </span>Proof of Theorem <span class="ltx_text ltx_ref_tag">6</span> (Discounted MDP Bounds)</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#A2.SS3" title="B.3 Proof of Theorem 7 (General Average-Reward MDP Bounds) ‣ Appendix B Proofs for General MDPs ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">B.3 </span>Proof of Theorem <span class="ltx_text ltx_ref_tag">7</span> (General Average-Reward MDP Bounds)</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2403.11477v1#A2.SS4" title="B.4 Proof of Theorems 3 and 4 (Lower Bounds) ‣ Appendix B Proofs for General MDPs ‣ Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">B.4 </span>Proof of Theorems <span class="ltx_text ltx_ref_tag">3</span> and <span class="ltx_text ltx_ref_tag">4</span> (Lower Bounds)</span></a></li> </ol> </li> </ol></nav> </nav> <div class="ltx_page_main"> <div class="ltx_page_content"> <div aria-label="Conversion errors have been found" class="package-alerts ltx_document" role="status"> <button aria-label="Dismiss alert" onclick="closePopup()"> <s
