paint-brush
Breaking Down the Inductive Proofs Behind Faster Value Iteration in RLby@anchoring

Breaking Down the Inductive Proofs Behind Faster Value Iteration in RL

by Anchoring
Anchoring HackerNoon profile picture

Anchoring

@anchoring

Anchoring provides a steady start, grounding decisions and perspectives in...

January 15th, 2025
Read on Terminal Reader
Read this story in a terminal
Print this story
Read this story w/o Javascript
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

Explore how Anchored Value Iteration (Anc-VI) accelerates convergence in dynamic programming and reinforcement learning
featured image - Breaking Down the Inductive Proofs Behind Faster Value Iteration in RL
1x
Read by Dr. One voice-avatar

Listen to this story

Anchoring HackerNoon profile picture
Anchoring

Anchoring

@anchoring

Anchoring provides a steady start, grounding decisions and perspectives in clarity and confidence.

About @anchoring
LEARN MORE ABOUT @ANCHORING'S
EXPERTISE AND PLACE ON THE INTERNET.
0-item

STORY’S CREDIBILITY

Academic Research Paper

Academic Research Paper

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

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

B Omitted proofs in Section 2

First, we prove the following lemma by induction.


image


image


image


image


image


image


image


image


Now, we present our key lemmas for the first rate of Theorem 2.


image


image


and let U¯ be the entire right hand side of inequality. Then, we have


image


By induction,


image


and let U¯ be the entire right hand side of inequality. Then, we have


image


Now, we prove the first rate of Theorem 2.


image


image


where the second inequality is from the condition.


By induction,


image


and let U¯ be the entire right hand side of inequality. Then, we have


image


Now, we prove the second rates of Theorem 2.


image


This paper is available on arxiv under CC BY 4.0 DEED license.


L O A D I N G
. . . comments & more!

About Author

Anchoring HackerNoon profile picture
Anchoring@anchoring
Anchoring provides a steady start, grounding decisions and perspectives in clarity and confidence.

TOPICS

THIS ARTICLE WAS FEATURED IN...

Permanent on Arweave
Read on Terminal Reader
Read this story in a terminal
 Terminal
Read this story w/o Javascript
Read this story w/o Javascript
 Lite
Also published here
Hackernoon
X
Bsky
X REMOVE AD