Authors:
(1) Jongmin Lee, Department of Mathematical Science, Seoul National University;
(2) Ernest K. Ryu, Department of Mathematical Science, Seoul National University and Interdisciplinary Program in Artificial Intelligence, Seoul National University. Abstract and 1 Introduction 1.1 Notations and preliminaries 1.2 Prior works 2 Anchored Value Iteration 2.1 Accelerated rate for Bellman consistency operator 2.2 Accelerated rate for Bellman optimality opera 3 Convergence when y=1 4 Complexity lower bound 5 Approximate Anchored Value Iteration 6 Gauss–Seidel Anchored Value Iteration 7 Conclusion, Acknowledgments and Disclosure of Funding and References A Preliminaries B Omitted proofs in Section 2 C Omitted proofs in Section 3 D Omitted proofs in Section 4 E Omitted proofs in Section 5 F Omitted proofs in Section 6 G Broader Impacts H Limitations 4 Complexity lower bound We now present a complexity lower bound establishing optimality of Anc-VI. The so-called “span condition” of Theorem 5 is arguably very natural and is satisfied by standard VI and Anc-VI. The span condition is commonly used in the construction of complexity lower bounds on first-order optimization methods [13, 14, 23, 25, 59, 65] and has been used in the prior state-ofthe-art lower bound for standard VI [37, Theorem 3]. However, designing an algorithm that breaks the lower bound of Theorem 5 by violating the span condition remains a possibility. In optimization theory, there is precedence of lower bounds being broken by violating seemingly natural and minute conditions [35, 40, 98]. This paper is available on arxiv under CC BY 4.0 DEED license. Authors: (1) Jongmin Lee, Department of Mathematical Science, Seoul National University; (2) Ernest K. Ryu, Department of Mathematical Science, Seoul National University and Interdisciplinary Program in Artificial Intelligence, Seoul National University. Authors: Authors: (1) Jongmin Lee, Department of Mathematical Science, Seoul National University; (2) Ernest K. Ryu, Department of Mathematical Science, Seoul National University and Interdisciplinary Program in Artificial Intelligence, Seoul National University. Abstract and 1 Introduction Abstract and 1 Introduction 1.1 Notations and preliminaries 1.1 Notations and preliminaries 1.2 Prior works 1.2 Prior works 2 Anchored Value Iteration 2 Anchored Value Iteration 2.1 Accelerated rate for Bellman consistency operator 2.1 Accelerated rate for Bellman consistency operator 2.2 Accelerated rate for Bellman optimality opera 2.2 Accelerated rate for Bellman optimality opera 3 Convergence when y=1 3 Convergence when y=1 4 Complexity lower bound 4 Complexity lower bound 5 Approximate Anchored Value Iteration 5 Approximate Anchored Value Iteration 6 Gauss–Seidel Anchored Value Iteration 6 Gauss–Seidel Anchored Value Iteration 7 Conclusion, Acknowledgments and Disclosure of Funding and References 7 Conclusion, Acknowledgments and Disclosure of Funding and References A Preliminaries A Preliminaries B Omitted proofs in Section 2 B Omitted proofs in Section 2 C Omitted proofs in Section 3 C Omitted proofs in Section 3 D Omitted proofs in Section 4 D Omitted proofs in Section 4 E Omitted proofs in Section 5 E Omitted proofs in Section 5 F Omitted proofs in Section 6 F Omitted proofs in Section 6 G Broader Impacts G Broader Impacts H Limitations H Limitations 4 Complexity lower bound We now present a complexity lower bound establishing optimality of Anc-VI. The so-called “span condition” of Theorem 5 is arguably very natural and is satisfied by standard VI and Anc-VI. The span condition is commonly used in the construction of complexity lower bounds on first-order optimization methods [13, 14, 23, 25, 59, 65] and has been used in the prior state-ofthe-art lower bound for standard VI [37, Theorem 3]. However, designing an algorithm that breaks the lower bound of Theorem 5 by violating the span condition remains a possibility. In optimization theory, there is precedence of lower bounds being broken by violating seemingly natural and minute conditions [35, 40, 98]. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Anc-VI Sets a New Standard for Reinforcement Learning Optimization

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Breaking Down the Inductive Proofs Behind Faster Value Iteration in RL

The Future of Virtual Identities in an AI-powered Metaverse

Why Human Touch Still Matters in Automated Process Testing

Why People, Platforms, and Process Drift Shape AB-BPM’s Future

How a BPM Dream Team Ranked the Risks and Tools for AB-BPM

Breaking Down the Inductive Proofs Behind Faster Value Iteration in RL

The Future of Virtual Identities in an AI-powered Metaverse

Why Human Touch Still Matters in Automated Process Testing

Why People, Platforms, and Process Drift Shape AB-BPM’s Future

How a BPM Dream Team Ranked the Risks and Tools for AB-BPM

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps