Body: <p>In my implementation of Thompson Sampling (TS) for online Reinforcement Learning, my distribution for selecting <span class="math-container">$a$</span> is <span class="math-container">$\mathcal{N}(Q(s, a), \frac{1}{C(s,a)+1})$</span>, where <span class="math-container">$C(s,a)$</span> is the number of times <span class="math-container">$a$</span> has been picked in <span class="math-container">$s$</span>.</p>
  <p>However, I found that this does not work well in some cases depending on the magnitude of <span class="math-container">$Q(s,a)$</span>. For example, if <span class="math-container">$Q(s_i,a_1) = 100$</span>, and <span class="math-container">$C(s_i,a_1) = 1$</span>, then then this gives a standard deviation of 0.5, which is extremely confident even though the action has only been picked once. Compare that to <span class="math-container">$a_2$</span> which may be the optimal action but has never been picked, so <span class="math-container">$Q(s_i, a_2) = 0$</span> and <span class="math-container">$C(s_i,a_2) = 0$</span>. It is unlikely that TS will ever pick <span class="math-container">$a_2$</span>.</p>
  <p>So, how do I solve this problem?</p>
  <p>I tried normalizing the Q-values such that they range from 0 to 1, but the algorithm returns much lower total returns. I think I have to adapt the magnitude of the standard deviations relative to the Q-values as well. Doing it for 1 normal distribution is pretty straightforward, but I can't figure out how to do it for multiple distributions which have to take into consideration of the other distributions.</p>
  <p>Edit: Counts should be <span class="math-container">$C(s,a)$</span> instead of <span class="math-container">$C(s)$</span> as Neil pointed out</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-22T13:35:02.533Z
Comments.Text: "if $Q(s_i,a_1) = 100$, and $C(a_1) = 1$, then..." in your imagined scenario, you have made a very large update to $Q(s_i,a_1)$ with either 0 or 1 samples from it - is this actually possible with the learning mechanism you are using, e.g. are you processing rewards such that $\alpha \times r_t$ could make a $+100$ value update in a single step? This is salient, because there is no need to worry about and attempt to fix numerical problems that don't occur in practice.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-22T13:59:45.377Z
Comments.Text: Counts should be s,a. I have edited the question. I am selecting the action with the highest sampled Q-value.
Comments.UserDisplayName: Kevin
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-22T14:02:17.127Z
Comments.Text: I have a learning rate of 0.1, I didn't include it, perhaps I should have. even then, it doesn't change the issue where $\mathcal{N}(10, 0.5)$ for $a_1$ is still going to be picked over $a_2$ with distribution $\mathcal{N}(0, 1)$.
Comments.UserDisplayName: Kevin
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-04-17T19:25:44.913Z
Comments.Text: What about using the advantage function $A(s,a)=Q(s,a) - V(s)$ instead of $Q(s,a)$? It should have a much lower variance, and, indeed, you should be able to compute the value function to do so.
Comments.UserDisplayName: Luca Anzalone
Tags: <reinforcement-learning><online-learning><normalisation><thompson-sampling><normal-distribution>
Title: Normalizing Normal Distributions in Thompson Sampling for online Reinforcement Learning
UserDisplayName: Kevin
ThreadText: # Normalizing Normal Distributions in Thompson Sampling for online Reinforcement Learning
  
  (Asked by: username_0 on 2019-11-22)
  
  In my implementation of Thompson Sampling (TS) for online Reinforcement Learning, my distribution for selecting $a$ is $\mathcal{N}(Q(s, a), \frac{1}{C(s,a)+1})$, where $C(s,a)$ is the number of times $a$ has been picked in $s$.
  
  However, I found that this does not work well in some cases depending on the magnitude of $Q(s,a)$. For example, if $Q(s\_i,a\_1) = 100$, and $C(s\_i,a\_1) = 1$, then then this gives a standard deviation of 0.5, which is extremely confident even though the action has only been picked once. Compare that to $a\_2$ which may be the optimal action but has never been picked, so $Q(s\_i, a\_2) = 0$ and $C(s\_i,a\_2) = 0$. It is unlikely that TS will ever pick $a\_2$.
  
  So, how do I solve this problem?
  
  I tried normalizing the Q-values such that they range from 0 to 1, but the algorithm returns much lower total returns. I think I have to adapt the magnitude of the standard deviations relative to the Q-values as well. Doing it for 1 normal distribution is pretty straightforward, but I can't figure out how to do it for multiple distributions which have to take into consideration of the other distributions.
  
  Edit: Counts should be $C(s,a)$ instead of $C(s)$ as Neil pointed out
  
  **Tags:** reinforcement-learning, online-learning, normalisation, thompson-sampling, normal-distribution
  > **Comments:**
  > **username_1**: "if $Q(s_i,a_1) = 100$, and $C(a_1) = 1$, then..." in your imagined scenario, you have made a very large update to $Q(s_i,a_1)$ with either 0 or 1 samples from it - is this actually possible with the learning mechanism you are using, e.g. are you processing rewards such that $\alpha \times r_t$ could make a $+100$ value update in a single step? This is salient, because there is no need to worry about and attempt to fix numerical problems that don't occur in practice.  
  > **username_0**: Counts should be s,a. I have edited the question. I am selecting the action with the highest sampled Q-value.  
  > **username_0**: I have a learning rate of 0.1, I didn't include it, perhaps I should have. even then, it doesn't change the issue where $\mathcal{N}(10, 0.5)$ for $a_1$ is still going to be picked over $a_2$ with distribution $\mathcal{N}(0, 1)$.  
  > **username_2**: What about using the advantage function $A(s,a)=Q(s,a) - V(s)$ instead of $Q(s,a)$? It should have a much lower variance, and, indeed, you should be able to compute the value function to do so.  
  
  ---
  
  ## 0 answers
  
  