Answers.Body: <p>The paper <a href="https://www.cis.upenn.edu/~mkearns/papers/tdlambda.pdf" rel="nofollow noreferrer">"Bias-Variance" Error Bounds for Temporal Difference Updates</a> (2000) by M. Kearns and S. Singh provides error bounds for temporal-difference algorithms, i.e. TD(<span class="math-container">$k$</span>) and TD(<span class="math-container">$\lambda$</span>) (see <a href="https://www.cis.upenn.edu/~mkearns/papers/tdlambda.pdf#page=3" rel="nofollow noreferrer">theorem 1</a> and <a href="https://www.cis.upenn.edu/~mkearns/papers/tdlambda.pdf#page=5" rel="nofollow noreferrer">theorem 2</a>, respectively). Note that both TD(<span class="math-container">$k$</span>) and TD(<span class="math-container">$\lambda$</span>) include TD(<span class="math-container">$0$</span>) as a special case.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T07:50:51.527Z
Answers.Text: I'm confused, is this for situations where the environment states can be enumerated or does it apply in general? I didn't see a parametrization.
Answers.UserDisplayName: FourierFlux
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T20:54:45.860Z
Answers.Text: @FourierFlux Do you mean if they assume that the state space is discrete? I need to read this paper again. It was a long time ago that I skimmed through it.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-15T19:33:30.397Z
Answers.LastActivityDate: 2020-04-15T19:33:30.397Z
Answers.UserDisplayName: nbro
Body: <p>Is there any known error bounds for the TD(0) algorithm for the value function after a finite number of iterations?</p>
  
  <p><span class="math-container">$$ \Delta_t=\max_{s \in \mathcal{S}}|v_t(s)-v_\pi(s)|$$</span>
  <span class="math-container">$$v_{t+1}(s_t)=v_t(s_t)+\alpha(r+v_t(s_{t+1})-v_t(s_t))$$</span></p>
  
Tags: <reinforcement-learning><temporal-difference-methods>
Title: Are there known error bounds for TD(0) with a constant learning rate?
UserDisplayName: KaneM
ThreadText: # Are there known error bounds for TD(0) with a constant learning rate?
  
  (Asked by: username_0 on 2020-03-25)
  
  Is there any known error bounds for the TD(0) algorithm for the value function after a finite number of iterations?
  
  $$ \Delta\_t=\max\_{s \in \mathcal{S}}|v\_t(s)-v\_\pi(s)|$$
  $$v\_{t+1}(s\_t)=v\_t(s\_t)+\alpha(r+v\_t(s\_{t+1})-v\_t(s\_t))$$
  
  **Tags:** reinforcement-learning, temporal-difference-methods
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-15. Score: 1
  
  The paper ["Bias-Variance" Error Bounds for Temporal Difference Updates](https://www.cis.upenn.edu/~mkearns/papers/tdlambda.pdf) (2000) by M. Kearns and S. Singh provides error bounds for temporal-difference algorithms, i.e. TD($k$) and TD($\lambda$) (see [theorem 1](https://www.cis.upenn.edu/~mkearns/papers/tdlambda.pdf#page=3) and [theorem 2](https://www.cis.upenn.edu/~mkearns/papers/tdlambda.pdf#page=5), respectively). Note that both TD($k$) and TD($\lambda$) include TD($0$) as a special case.
  
  > **Comments:**
  > **username_2**: I'm confused, is this for situations where the environment states can be enumerated or does it apply in general? I didn't see a parametrization.  
  > **username_1**: @FourierFlux Do you mean if they assume that the state space is discrete? I need to read this paper again. It was a long time ago that I skimmed through it.  
  
  ---
  
  