Answers.Body: <p>I am not strictly convinced that Q-learning should necessarily learn a singular optimal path.  Given infinite exploration, Q-learning should estimate the reward of all actions.  In a state where two actions have the same reward the tie should be broken randomly (giving all equal paths the same probability of being followed).  The remaining actions would have zero probability of being followed given a perfectly deterministic maximizing agent.</p>
  <p>In practice we do not explore infinitely or our estimators do not learn infinitely.  This might account for the perception that it finds a singular near optimal path.  Often the problem space is too large and our estimators too opaque to inspect what has actually been learned.  I would challenge to experiment with tabular Q-learning on a multi-armed bandit where more than one arm has equivalent rewards.</p>
  <p>So I guess my answer would be that the issue is unlikely to be with the learning method but with the learning hyper-parameters (learning rate, epsilon annealing rate, etc).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-09T19:20:13.990Z
Answers.Text: thank you so much for the insight. would you say the same about actor-critic? and does this problem have an official name so that i can find literature discussing it?
Answers.UserDisplayName: moe asal
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-09T19:13:15.087Z
Answers.LastActivityDate: 2024-04-09T20:01:49.940Z
Answers.LastEditDate: 2024-04-09T20:01:49.940Z
Answers.UserDisplayName: foreverska
Answers.Body: <p>Q-learning will indeed learn <strong>a</strong> trajectory, as they are all equivalent, and usually the resulting policy of a Q-learning algorithm is a greedy policy, which selects:
  <span class="math-container">$$
  a = argmax_a Q(s,a)
  $$</span>
  so, no matter what you do, the final policy in your case has to be deterministic.</p>
  <p>In the actor critic scenario, this is not obvious. Indeed, if two actions <span class="math-container">$a_0$</span> and <span class="math-container">$a_1$</span> lead to trajectories with the same expected return, when you update the actor using:
  <span class="math-container">$$
  \nabla J(\theta) \approx \mathbb{E}[G_t \nabla_\theta \ln \pi(a|s)]
  $$</span>
  you can clearly see that both the actions will be reinforced equally</p>
  <p>However, you have to consider that the overall objective of RL is to maximise:
  <span class="math-container">$$
  \mathbb{E}[\sum \gamma^tr_t]
  $$</span>
  In order to that to happen, going back to the previous scenario, any linear combination between the policy that always selects <span class="math-container">$a_0$</span> and the one that always selects <span class="math-container">$a_1$</span>, will be an optimal policy, as the all lead to the same solution (solution meant as expected sum of rewards)</p>
  <p>A very simple example of this, is by considering the trivial case where you have 2 bandits (think about slot machines) that give the same expected return <span class="math-container">$C$</span>: your policy return will be <span class="math-container">$V = p(a_0)C + p(a_1)C$</span>, clearly, any combination of the two probability lead to the same value (obviously having <span class="math-container">$p(a_0)C &gt; 0, p(a_1) &gt; 0, p(a_0) + p(a_1) = 1$</span>)</p>
  <p>However, luckily for you, there is an easy fix if you want the policy that not only maximizes the expected sum of rewards, but it's also as stochastic as possible, that is to introduce an entropy bonus
  <span class="math-container">$$
  \nabla J(\theta) \approx \mathbb{E}[G_t \nabla_\theta \ln \pi(a|s)] + \mathcal{H}(\pi)
  $$</span>
  And this solution, will select the policy <span class="math-container">$\pi$</span> that also maximises the entropy, thus making it as stochastic as possible, thus distributing equally the probability mass across actions that lead to trajectories with the same expected return</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-09T22:06:11.697Z
Answers.Text: Thank you. Your answer led me to this research paper that addresses my problem perfectly. For future readers: https://arxiv.org/pdf/1812.05905.pdf
Answers.UserDisplayName: moe asal
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T03:49:09.517Z
Answers.Text: @‍Alberto: Your last paragraph is wrong. Adding an entropy term *destroys* the optimality and the policy you get would generally **not** optimize expected return. Whether this is a good *heuristic* for the specific use-case or not is a totally separate question, but you cannot claim optimality. CC @moeasal
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T07:19:15.523Z
Answers.Text: I think that the entropy bonus needs to be weighted carefully, and potentially down over time. It may be useful initially to discover different equivalent trajectories, but it will also cause a preference towards action distributions that are not optimal when the entropy bonus is close to scale of the rest of the objective. Also, are you *sure* adding this bonus to the gradient works? I think that's equivalent to maximising the squared entropy measure - probably ok, but a little odd
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T07:21:30.960Z
Answers.Text: The entropy measure is probably some log sum over the probability distribution anyway, so this weirdly ends up looking a bit like L2 regularisation
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T08:28:41.297Z
Answers.Text: @NeilSlater yes it's the sum of log terms, though I'm not sure how you can end up with an L2 regularization...
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T09:18:44.430Z
Answers.Text: I mean it has the "rough feel" of L2 weight regularisation, except due to positive direction is about  largest distribution (as opposed to smallest individual numbers), and also of course it is not weights being impacted but output probabilities. And like regularisation, it's a balance between two potentially opposing objectives
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T15:01:37.883Z
Answers.Text: @NeilSlater i mean i hardly see appearing any squared term, but you can see it as something like adding $-||p(a)-1/N||^2$, thus giving a bonus the closer you are to to uniform ($N$ being the number of actions you can perform)
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T18:42:31.450Z
Answers.Text: @user21820 i agree with you that you are adding a small bias, however you can pretty clearly interpret it as a Lagrangian of the constrained problem which maximizes the entropy s.t. the policy value is the maximum
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-10T18:43:58.740Z
Answers.Text: @NeilSlater sorry, only now i saw your first comment… yes it works and it has been done many times, for example in the paper of SAC (though sure, it needs a scalar carefully chosen)
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-11T10:36:57.017Z
Answers.Text: The very fact that you need a constant weight on the bonus term already tells you that it cannot be correct. The closer the weight to zero, the closer to optimality. You can't have both optimality and preference for stochastic trajectories! Sure, we may want some trade-off, but you need to be clear about that.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-11T12:27:31.463Z
Answers.Text: @user21820 not sure how you can be so sure about it: assume we find the optimal policy without entropy with value $V^*$, then problem $\max \mathcal{H}(\pi) s.t. V(\pi) = V^*$ is for sure well defined, AND feasible (though maybe intractable) AND the solution is that the OP is looking for, but the "_the fact that you need a constant weight on the bonus term already tells you that it cannot be correct_" goes 100% against the concept of Lagrangian (Lagrange multipliers) in constrained optimization, so I'll suggest you to give it a look :)
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-11T12:30:29.900Z
Answers.Text: @user21820 after looking at that, I then suggest you take a look at the paper of PPO, where they use the Lagrange multiplier form of the loss when talking about the KL version of the objective, and show that with a dual descent mechanism,e you can be very close (note that the "constant" work in this comment section has been used only by you, I've never said that it needs a fixed value)
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-12T13:40:22.110Z
Answers.Text: I know the Lagrange multiplier technique, which is not at all the same as what you are doing. Optimizing entropy after optimizing the return value of course can be done, but you cannot do both simultaneously by just arbitrarily adding two terms. You are misunderstanding my use of the word "constant"; what I said was exactly in line with what @NeilSlater said, namely that you need to weight the two terms and gradually adjust the weights. You also agreed that you need 'carefully chosen' weights, and "very close" ≢ "optimal". My point is just that as written in your post it cannot be optimal.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-15T14:57:50.697Z
Answers.Text: @user21820 https://arxiv.org/pdf/1801.01290.pdf proof B.1... i would say that is pretty close...
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-09T21:40:37.597Z
Answers.LastActivityDate: 2024-04-09T21:40:37.597Z
Answers.UserDisplayName: Alberto
Body: <p>I am not an expert in reinforcement learning. I am applying it to my field of study.</p>
  <p>I am training a model such that given a state, it predicts the probability of taking an action for every action possible. As such the model can be described as M: S -&gt; P where P is the set of all probability vectors over A, the discrete action space. S is the set of all possible discrete states.</p>
  <p>The model takes actions stochastically to create a finite trajectory (I do not choose the action with maximum probability, instead, I sample trajectories). Multiple trajectories have the same reward (summed over the state-action units in the trajectory).</p>
  <p>Define G to be the set of trajectories with maximum reward sum.</p>
  <p>If I train such a model using any mainstream algorithm (Q-learning, actor-critic, etc.) the model will learn, loosely speaking, to maximize the probability of <strong>a</strong> trajectory from G. It will not learn a uniform distribution over the set G. Instead, probability will concentrate on a specific trajectory. This is not an exploration problem as far as I know, since even if the model <em>explores</em> every possible trajectory, probability will still concentrate on one trajectory. And it is not inherently a problem in reinforcement learning, it is specific to my use case.</p>
  <p>I would very much appreciate any references that tackle this problem. I am searching for an algorithm that produces a uniform distribution over the set G and a negligible probability for all other trajectories.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-04-09T18:53:40.930Z
Comments.Text: Are you attempting to build a model which finds all (or many) optimal policies in an environment?
Comments.UserDisplayName: foreverska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-04-09T19:01:02.017Z
Comments.Text: @foreverska yes, in a sense. All these optimal policies should be summarized by one model that, in a sense, samples uniformly from one of them.
Comments.UserDisplayName: moe asal
Tags: <reinforcement-learning><algorithm-request>
Title: Is there an algorithm that produces a uniform distribution over the set of trajectories with maximum reward sum?
UserDisplayName: moe asal
ThreadText: # Is there an algorithm that produces a uniform distribution over the set of trajectories with maximum reward sum?
  
  (Asked by: username_0 on 2024-04-09)
  
  I am not an expert in reinforcement learning. I am applying it to my field of study.
  
  I am training a model such that given a state, it predicts the probability of taking an action for every action possible. As such the model can be described as M: S -> P where P is the set of all probability vectors over A, the discrete action space. S is the set of all possible discrete states.
  
  The model takes actions stochastically to create a finite trajectory (I do not choose the action with maximum probability, instead, I sample trajectories). Multiple trajectories have the same reward (summed over the state-action units in the trajectory).
  
  Define G to be the set of trajectories with maximum reward sum.
  
  If I train such a model using any mainstream algorithm (Q-learning, actor-critic, etc.) the model will learn, loosely speaking, to maximize the probability of **a** trajectory from G. It will not learn a uniform distribution over the set G. Instead, probability will concentrate on a specific trajectory. This is not an exploration problem as far as I know, since even if the model *explores* every possible trajectory, probability will still concentrate on one trajectory. And it is not inherently a problem in reinforcement learning, it is specific to my use case.
  
  I would very much appreciate any references that tackle this problem. I am searching for an algorithm that produces a uniform distribution over the set G and a negligible probability for all other trajectories.
  
  **Tags:** reinforcement-learning, algorithm-request
  
  > **Comments:**
  > **username_1**: Are you attempting to build a model which finds all (or many) optimal policies in an environment?  
  > **username_0**: @username_1 yes, in a sense. All these optimal policies should be summarized by one model that, in a sense, samples uniformly from one of them.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2024-04-09. Score: 5 | Accepted answer
  
  Q-learning will indeed learn **a** trajectory, as they are all equivalent, and usually the resulting policy of a Q-learning algorithm is a greedy policy, which selects:
  $$
  a = argmax\_a Q(s,a)
  $$
  so, no matter what you do, the final policy in your case has to be deterministic.
  
  In the actor critic scenario, this is not obvious. Indeed, if two actions $a\_0$ and $a\_1$ lead to trajectories with the same expected return, when you update the actor using:
  $$
  \nabla J(\theta) \approx \mathbb{E}[G\_t \nabla\_\theta \ln \pi(a|s)]
  $$
  you can clearly see that both the actions will be reinforced equally
  
  However, you have to consider that the overall objective of RL is to maximise:
  $$
  \mathbb{E}[\sum \gamma^tr\_t]
  $$
  In order to that to happen, going back to the previous scenario, any linear combination between the policy that always selects $a\_0$ and the one that always selects $a\_1$, will be an optimal policy, as the all lead to the same solution (solution meant as expected sum of rewards)
  
  A very simple example of this, is by considering the trivial case where you have 2 bandits (think about slot machines) that give the same expected return $C$: your policy return will be $V = p(a\_0)C + p(a\_1)C$, clearly, any combination of the two probability lead to the same value (obviously having $p(a\_0)C > 0, p(a\_1) > 0, p(a\_0) + p(a\_1) = 1$)
  
  However, luckily for you, there is an easy fix if you want the policy that not only maximizes the expected sum of rewards, but it's also as stochastic as possible, that is to introduce an entropy bonus
  $$
  \nabla J(\theta) \approx \mathbb{E}[G\_t \nabla\_\theta \ln \pi(a|s)] + \mathcal{H}(\pi)
  $$
  And this solution, will select the policy $\pi$ that also maximises the entropy, thus making it as stochastic as possible, thus distributing equally the probability mass across actions that lead to trajectories with the same expected return
  
  > **Comments:**
  > **username_0**: Thank you. Your answer led me to this research paper that addresses my problem perfectly. For future readers: https://arxiv.org/pdf/1812.05905.pdf  
  > **username_3**: @‍username_2: Your last paragraph is wrong. Adding an entropy term *destroys* the optimality and the policy you get would generally **not** optimize expected return. Whether this is a good *heuristic* for the specific use-case or not is a totally separate question, but you cannot claim optimality. CC @username_0  
  > **username_4**: I think that the entropy bonus needs to be weighted carefully, and potentially down over time. It may be useful initially to discover different equivalent trajectories, but it will also cause a preference towards action distributions that are not optimal when the entropy bonus is close to scale of the rest of the objective. Also, are you *sure* adding this bonus to the gradient works? I think that's equivalent to maximising the squared entropy measure - probably ok, but a little odd  
  > **username_4**: The entropy measure is probably some log sum over the probability distribution anyway, so this weirdly ends up looking a bit like L2 regularisation  
  > **username_2**: @username_4 yes it's the sum of log terms, though I'm not sure how you can end up with an L2 regularization...  
  > **username_4**: I mean it has the "rough feel" of L2 weight regularisation, except due to positive direction is about  largest distribution (as opposed to smallest individual numbers), and also of course it is not weights being impacted but output probabilities. And like regularisation, it's a balance between two potentially opposing objectives  
  > **username_2**: @username_4 i mean i hardly see appearing any squared term, but you can see it as something like adding $-||p(a)-1/N||^2$, thus giving a bonus the closer you are to to uniform ($N$ being the number of actions you can perform)  
  > **username_2**: @username_3 i agree with you that you are adding a small bias, however you can pretty clearly interpret it as a Lagrangian of the constrained problem which maximizes the entropy s.t. the policy value is the maximum  
  > **username_2**: @username_4 sorry, only now i saw your first comment… yes it works and it has been done many times, for example in the paper of SAC (though sure, it needs a scalar carefully chosen)  
  > **username_3**: The very fact that you need a constant weight on the bonus term already tells you that it cannot be correct. The closer the weight to zero, the closer to optimality. You can't have both optimality and preference for stochastic trajectories! Sure, we may want some trade-off, but you need to be clear about that.  
  > **username_2**: @username_3 not sure how you can be so sure about it: assume we find the optimal policy without entropy with value $V^*$, then problem $\max \mathcal{H}(\pi) s.t. V(\pi) = V^*$ is for sure well defined, AND feasible (though maybe intractable) AND the solution is that the OP is looking for, but the "_the fact that you need a constant weight on the bonus term already tells you that it cannot be correct_" goes 100% against the concept of Lagrangian (Lagrange multipliers) in constrained optimization, so I'll suggest you to give it a look :)  
  > **username_2**: @username_3 after looking at that, I then suggest you take a look at the paper of PPO, where they use the Lagrange multiplier form of the loss when talking about the KL version of the objective, and show that with a dual descent mechanism,e you can be very close (note that the "constant" work in this comment section has been used only by you, I've never said that it needs a fixed value)  
  > **username_3**: I know the Lagrange multiplier technique, which is not at all the same as what you are doing. Optimizing entropy after optimizing the return value of course can be done, but you cannot do both simultaneously by just arbitrarily adding two terms. You are misunderstanding my use of the word "constant"; what I said was exactly in line with what @username_4 said, namely that you need to weight the two terms and gradually adjust the weights. You also agreed that you need 'carefully chosen' weights, and "very close" ≢ "optimal". My point is just that as written in your post it cannot be optimal.  
  > **username_2**: @username_3 https://arxiv.org/pdf/1801.01290.pdf proof B.1... i would say that is pretty close...  
  
  ---
  
  ### Answer by username_1 on 2024-04-09. Score: 2
  
  I am not strictly convinced that Q-learning should necessarily learn a singular optimal path. Given infinite exploration, Q-learning should estimate the reward of all actions. In a state where two actions have the same reward the tie should be broken randomly (giving all equal paths the same probability of being followed). The remaining actions would have zero probability of being followed given a perfectly deterministic maximizing agent.
  
  In practice we do not explore infinitely or our estimators do not learn infinitely. This might account for the perception that it finds a singular near optimal path. Often the problem space is too large and our estimators too opaque to inspect what has actually been learned. I would challenge to experiment with tabular Q-learning on a multi-armed bandit where more than one arm has equivalent rewards.
  
  So I guess my answer would be that the issue is unlikely to be with the learning method but with the learning hyper-parameters (learning rate, epsilon annealing rate, etc).
  
  > **Comments:**
  > **username_0**: thank you so much for the insight. would you say the same about actor-critic? and does this problem have an official name so that i can find literature discussing it?  
  
  ---
  
  