Answers.Body: <p>I had just successfully implemented RLS when I found this question. In fact, I wanted to extend it to the mini batch setting, just like you (which I did!).</p>
  <p>RLS is derived using the <a href="https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula" rel="nofollow noreferrer">Sherman-Morrison formula</a>, which is specific for rank-1 updates. We'd need to use its generalization for rank-n updates, the <a href="https://en.wikipedia.org/wiki/Woodbury_matrix_identity" rel="nofollow noreferrer">Woodbury Matrix Identity</a>. By looking at the <a href="https://matousc89.github.io/padasip/sources/filters/rls.html" rel="nofollow noreferrer">RLS formula</a>, the Sherman-Morrison formula becomes evident, and the conversion can be made quite easily. My solution in Python with PyTorch is this:</p>
  <pre><code>R = (R - (R @ x.T @ torch.linalg.inv(l * torch.eye(k) + x @ R @ x.T) @ x @ R) ) / l
  </code></pre>
  <p>where <span class="math-container">$k$</span> is the mini batch size and <span class="math-container">$l$</span> is the forgetting factor (which can be set to 1 to give the same result as OLS). The transposes are inverted, since I use batch_size x input_dim format for <span class="math-container">$x$</span>. It gives me the same result as the rank-1 updates, except for a <span class="math-container">$-0.05\%$</span> difference in accuracy on MNIST in my experiments, which I attribute to rounding errors and such. If anyone finds any error in my formula (or any improvement to it), please, leave a comment :)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-07T22:39:28.620Z
Answers.LastActivityDate: 2024-01-07T22:39:28.620Z
Answers.UserDisplayName: rcpinto
Body: <p>For my application I am considering a learning problem where I simulate a bunch of episodes say '<span class="math-container">$n$</span>' first, and than carry out the recursive least squares update. Similar to <span class="math-container">$TD(1)$</span>.</p>
  <p>I know that RLS can be used to update parameters being learned as they arrive. This can be done efficiently for single data point and the derivations are easily available online and also easy to understand.</p>
  <p>However for my case I am looking for same equations when data arrive as a mini batch and not a single data point at a time. I could not find any material regarding RLS for mini batches.</p>
  <p>According to my understanding the same equations can be also used by appropriately considering matrix dimensions. However I do not know if this is valid.</p>
  <p>What are the alternatives to be used?</p>
  
Tags: <reinforcement-learning><function-approximation><weights><temporal-difference-methods><finite-markov-decision-process>
Title: Recursive Least squares (RLS) for mini batch
UserDisplayName: Prakash Gawas
ThreadText: # Recursive Least squares (RLS) for mini batch
  
  (Asked by: username_0 on 2021-07-27)
  
  For my application I am considering a learning problem where I simulate a bunch of episodes say '$n$' first, and than carry out the recursive least squares update. Similar to $TD(1)$.
  
  I know that RLS can be used to update parameters being learned as they arrive. This can be done efficiently for single data point and the derivations are easily available online and also easy to understand.
  
  However for my case I am looking for same equations when data arrive as a mini batch and not a single data point at a time. I could not find any material regarding RLS for mini batches.
  
  According to my understanding the same equations can be also used by appropriately considering matrix dimensions. However I do not know if this is valid.
  
  What are the alternatives to be used?
  
  **Tags:** reinforcement-learning, function-approximation, weights, temporal-difference-methods, finite-markov-decision-process
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-01-07. Score: 0
  
  I had just successfully implemented RLS when I found this question. In fact, I wanted to extend it to the mini batch setting, just like you (which I did!).
  RLS is derived using the Sherman-Morrison formula, which is specific for rank-1 updates. We'd need to use its generalization for rank-n updates, the Woodbury Matrix Identity. By looking at the RLS formula, the Sherman-Morrison formula becomes evident, and the conversion can be made quite easily. My solution in Python with PyTorch is this:
  R = (R - (R @ x.T @ torch.linalg.inv(l * torch.eye(k) + x @ R @ x.T) @ x @ R) ) / l
  
  where $k$ is the mini batch size and $l$ is the forgetting factor (which can be set to 1 to give the same result as OLS). The transposes are inverted, since I use batch_size x input_dim format for $x$. It gives me the same result as the rank-1 updates, except for a $-0.05\%$ difference in accuracy on MNIST in my experiments, which I attribute to rounding errors and such. If anyone finds any error in my formula (or any improvement to it), please, leave a comment :)
  
  
  ---
  
  