Answers.Body: <p>When the next state selection is not driven by any meaningful dynamics i.e. it is independent of starting state <span class="math-container">$s$</span> and action taken <span class="math-container">$a$</span>, but the rewards received do depend somehow on the <span class="math-container">$s$</span> and <span class="math-container">$a$</span>, then the MDP you describe also fits with something called a <a href="https://towardsdatascience.com/contextual-bandits-and-reinforcement-learning-6bdfeaece72a" rel="nofollow noreferrer">Contextual Bandit Problem</a> where there is no control over state due to action choice, and thus no incentive to choose actions other than for their potential for immediate reward.</p>
  
  <p>Any algorithm capable of solving a full MDP can also be put to use attempting to solve a contextual bandit problem, as the MDP framework is a strictly more general case of the contextual bandit problem, and can model such an environment. However, this is typically going to be inefficient, as MDP solvers make no assumptions about state transition dynamics and need to experience and learn them. Whilst if you start with an algorithm designed to solve a contextual bandit problem, you have the assumption of randomised state built in to the algorithm, it does not need to be learned, and the learning process should be more efficient.</p>
  
  <p>Alternatively, if you only have RL solvers available, you can reduce variance and get the same effective policy by setting discount factor, <span class="math-container">$\gamma = 0$</span>. </p>
  
  <p>If for some reason you still want or need a long-term discounted value prediction from your policy, you can take the mean predicted value of some random states (or even of all the states if there are few enough of them) and multiply by <span class="math-container">$\frac{1}{1-\gamma}$</span> for whatever discount factor you want to know it for. Or if predicting for a time horizon, just multiply by number of steps to the horizon.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-05T08:49:28.517Z
Answers.LastActivityDate: 2019-05-05T17:05:59.460Z
Answers.LastEditDate: 2019-05-05T17:05:59.460Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Convergence guarantees for basic RL algorithms like policy gradient / actor-critic methods make no assumptions about the dynamics of the MDP. So, theoretically, you don't need to change much.</p>
  
  <p>Practically, when the number of possible trajectories from any given state is so high, the return from each state will have high variance. This means you'll have to collect much more experience for your estimates of expected return to converge to their true values. Intuitively, an environment with high uncertainty requires the agent to do more knowledge-gathering to behave optimally.</p>
  
  <p>My real advice to you depends on what exactly you're trying to do. If you want to have the kind of agent that <strong>could</strong> learn to behave well in an extremely random environment, then all you need to worry about is giving it enough experience to learn from. </p>
  
  <p>(Your agent should also take a little longer before deciding it's "confident" in its evaluation of different states. That is, don't behave greedily before you're sure your estimates are accurate. Explore adequately. This advice is only relevant if your MDP dynamics aren't actually completely uniform.)</p>
  
  <p>If, however, you want to train an RL agent <strong>specifically</strong> to solve a problem formulated as an MDP with <strong>uniformly</strong> random dynamics, then I would tell you to not waste your time. We know before spending the computation that all policies would be equally good/bad in this setting. Since actions are irrelevant to the environment, it would be inefficient to deploy an RL agent that will only learn that which action it takes doesn't matter.</p>
  
  <hr>
  
  <p>As noted in the comments, the last paragraph is only true when reward from each state-action pair <span class="math-container">$(s,a)$</span> is also uniformly random. If it is not, just being aware of the high variance and giving your agent a lot of experience should do the trick.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-05T08:45:52.310Z
Answers.Text: @NeilSlater You're right. I was assuming that reward is jointly determined with the next state. I'll edit to make a note, but is that not usually the case?
Answers.UserDisplayName: Philip Raeisghasem
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-05T12:50:07.450Z
Answers.Text: The reward function here depends on both state and action and is not uniformly random. I guess in that case your last paragraph is not relevant?
Answers.UserDisplayName: grok
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-05T06:42:57.857Z
Answers.LastActivityDate: 2019-05-05T08:51:17.900Z
Answers.LastEditDate: 2019-05-05T08:51:17.900Z
Answers.UserDisplayName: Philip Raeisghasem
Body: <p>Suppose I have an MDP <span class="math-container">$(S, A, p, R)$</span> where the <span class="math-container">$p(s_j|s_i,a_i)$</span> is uniform, i.e given an state <span class="math-container">$s_i$</span> and an action <span class="math-container">$a_i$</span> all states <span class="math-container">$s_j$</span> are equally probable.</p>
  
  <p>Now I want to find an optimal policy for this MDP. Can I just apply the usual methods like policy gradients, actor-critic to find the optimal policy for this MDP? Or is there something I should be worried about?</p>
  
  <p>At least, in theory, it shouldn't make any difference. But I'm wondering are there any practical considerations I should be worried about? Should the discount factor, in this case, be high?</p>
  
  <p>The reward function here depends both on states and actions and is not uniformly random.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-05T08:41:35.107Z
Comments.Text: Hi, could you clarify what the reward function $r(s,a)$ depends on? An answer needs to know whether starting state $s$ is relevant to the reward, and also the action $a$.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-05T12:46:37.730Z
Comments.Text: @NeilSlater The reward function depends both on states and actions. The reward function is not uniformly random.
Comments.UserDisplayName: grok
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-05T16:55:32.727Z
Comments.Text: Thanks for clarifying that. There is no need to signal edits in the question (anyone who is interested can see the edit history), so I have removed that bit.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><markov-decision-process>
Title: Reinforcement learning with uniformly random dynamics
UserDisplayName: grok
ThreadText: # Reinforcement learning with uniformly random dynamics
  
  (Asked by: username_0 on 2019-05-04)
  
  Suppose I have an MDP $(S, A, p, R)$ where the $p(s\_j|s\_i,a\_i)$ is uniform, i.e given an state $s\_i$ and an action $a\_i$ all states $s\_j$ are equally probable.
  
  Now I want to find an optimal policy for this MDP. Can I just apply the usual methods like policy gradients, actor-critic to find the optimal policy for this MDP? Or is there something I should be worried about?
  
  At least, in theory, it shouldn't make any difference. But I'm wondering are there any practical considerations I should be worried about? Should the discount factor, in this case, be high?
  
  The reward function here depends both on states and actions and is not uniformly random.
  
  **Tags:** reinforcement-learning, markov-decision-process
  
  > **Comments:**
  > **username_1**: Hi, could you clarify what the reward function $r(s,a)$ depends on? An answer needs to know whether starting state $s$ is relevant to the reward, and also the action $a$.  
  > **username_0**: @username_1 The reward function depends both on states and actions. The reward function is not uniformly random.  
  > **username_1**: Thanks for clarifying that. There is no need to signal edits in the question (anyone who is interested can see the edit history), so I have removed that bit.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2019-05-05. Score: 3
  
  When the next state selection is not driven by any meaningful dynamics i.e. it is independent of starting state $s$ and action taken $a$, but the rewards received do depend somehow on the $s$ and $a$, then the MDP you describe also fits with something called a [Contextual Bandit Problem](https://towardsdatascience.com/contextual-bandits-and-reinforcement-learning-6bdfeaece72a) where there is no control over state due to action choice, and thus no incentive to choose actions other than for their potential for immediate reward.
  
  Any algorithm capable of solving a full MDP can also be put to use attempting to solve a contextual bandit problem, as the MDP framework is a strictly more general case of the contextual bandit problem, and can model such an environment. However, this is typically going to be inefficient, as MDP solvers make no assumptions about state transition dynamics and need to experience and learn them. Whilst if you start with an algorithm designed to solve a contextual bandit problem, you have the assumption of randomised state built in to the algorithm, it does not need to be learned, and the learning process should be more efficient.
  
  Alternatively, if you only have RL solvers available, you can reduce variance and get the same effective policy by setting discount factor, $\gamma = 0$.
  
  If for some reason you still want or need a long-term discounted value prediction from your policy, you can take the mean predicted value of some random states (or even of all the states if there are few enough of them) and multiply by $\frac{1}{1-\gamma}$ for whatever discount factor you want to know it for. Or if predicting for a time horizon, just multiply by number of steps to the horizon.
  
  
  ---
  
  ### Answer by username_2 on 2019-05-05. Score: 2
  
  Convergence guarantees for basic RL algorithms like policy gradient / actor-critic methods make no assumptions about the dynamics of the MDP. So, theoretically, you don't need to change much.
  
  Practically, when the number of possible trajectories from any given state is so high, the return from each state will have high variance. This means you'll have to collect much more experience for your estimates of expected return to converge to their true values. Intuitively, an environment with high uncertainty requires the agent to do more knowledge-gathering to behave optimally.
  
  My real advice to you depends on what exactly you're trying to do. If you want to have the kind of agent that **could** learn to behave well in an extremely random environment, then all you need to worry about is giving it enough experience to learn from.
  
  (Your agent should also take a little longer before deciding it's "confident" in its evaluation of different states. That is, don't behave greedily before you're sure your estimates are accurate. Explore adequately. This advice is only relevant if your MDP dynamics aren't actually completely uniform.)
  
  If, however, you want to train an RL agent **specifically** to solve a problem formulated as an MDP with **uniformly** random dynamics, then I would tell you to not waste your time. We know before spending the computation that all policies would be equally good/bad in this setting. Since actions are irrelevant to the environment, it would be inefficient to deploy an RL agent that will only learn that which action it takes doesn't matter.
  
  ---
  
  As noted in the comments, the last paragraph is only true when reward from each state-action pair $(s,a)$ is also uniformly random. If it is not, just being aware of the high variance and giving your agent a lot of experience should do the trick.
  
  > **Comments:**
  > **username_2**: @username_1 You're right. I was assuming that reward is jointly determined with the next state. I'll edit to make a note, but is that not usually the case?  
  > **username_0**: The reward function here depends on both state and action and is not uniformly random. I guess in that case your last paragraph is not relevant?  
  
  ---
  
  