Answers.Body: <p>My understanding of your environment is:</p>
  <ul>
  <li><p>The batch number <span class="math-container">$b$</span> is the same thing as a time step <span class="math-container">$t$</span>. Each batch is associated with a single static representation of the environment, the agent makes one decision, then receives a reward and a next state. I am using <span class="math-container">$t$</span> instead of <span class="math-container">$b$</span> to match the usual name seen in RL.</p>
  </li>
  <li><p>There is a <em>generator</em> which can be in a state <span class="math-container">$s_t$</span>, initially unknown for <span class="math-container">$s_0$</span>.</p>
  </li>
  <li><p>Each time step, <span class="math-container">$t$</span>, the <em>generator</em> creates a batch of &quot;pebbles&quot;. The generator state <span class="math-container">$s_t$</span> determines the output of the generator, and is the <em>only</em> non-random influence on the contents of each batch - it controls the possible rewards plus the possible next states.</p>
  </li>
  <li><p>Selecting a specific pebble from the batch returns an immediate reward <span class="math-container">$r_{t+1}$</span> plus sets the next state <span class="math-container">$s_{t+1}$</span>. This is the agent's action, and it can choose any pebble from the batch as its action <span class="math-container">$a_t$</span>.</p>
  </li>
  <li><p>The agent can see the values of <span class="math-container">$r_{t+1}$</span> and <span class="math-container">$s_{t+1}$</span> associated with each pebble before making its selection.</p>
  </li>
  </ul>
  <p>This is a slightly unusual setup for an MDP, but I think it is still a valid MDP, and the expected return can still be maximised using reinforcement learning. One important detail is that although you have a discrete list of actions in each batch, the action index values look like they are meaningless. Your action choice is really to choose the next state <span class="math-container">$s_{t+1}$</span> from a presented list of available states. Your action space is therefore continuous, not discrete, even though at each step you are selecting from a discrete set of actions.</p>
  <p>The environment design is different enough from standard that most off-the-shelf RL agent libraries will not work for you. However, you can take advantage of this knowledge of the action space, and the fact that there is no other meaningful state than that selected by the agent when it chooses a pebble, to learn state values efficiently.</p>
  <p>I would suggest you use a variant of Q-Learning, based on the &quot;afterstate&quot; values that you are selecting. You can train a neural network to approximate the state value function <span class="math-container">$\hat{v}(s,\theta)$</span> and you have a choice whether to use discounted returns or an average reward setting. When deciding the greedy target policy, you will want to select according to</p>
  <p><span class="math-container">$$\pi = \text{argmax}_i (r_i + \gamma \hat{v}(s_i,\theta))$$</span></p>
  <p>for discounted return. For Q learning, technically you should also store the whole batch output in experience replay, because the TD target will be</p>
  <p><span class="math-container">$$g = \text{max}_i (r_i + \gamma \hat{v}(s_i,\theta))$$</span></p>
  <p>and you won't know what this max will be later at the time of storing the memory. There may be ways around that - for instance you could use SARSA updates based on the actual action taken, or you could store the value of <span class="math-container">$g$</span>. However, these would be less sample efficient and you would need to discard the memory at a faster rate, before it became too out of date with respect tothe current policy.</p>
  <p>I think an average reward will be closer to your stated goal of generating highest expected reward from each individual batch, but I am not 100% certain how to set up the policy for that. Whilst a discounted return may end up preferring a high immediate reward in some circumstances. However, you may be able to get near identical behaviour by setting <span class="math-container">$\gamma$</span> high enough (e.g. <span class="math-container">$0.99$</span> or higher) in the more familiar discounted return setting.</p>
  <p>The efficiency of this approach will depend on how easy it is for the agent to learn the mapping between states and the quality of the next batch. However, you should have a higher sample efficiency when selecting by afterstate, because the agent does not need to learn separately how actions relate to states.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-27T12:47:45.633Z
Answers.LastActivityDate: 2021-10-28T09:44:43.040Z
Answers.LastEditDate: 2021-10-28T09:44:43.040Z
Answers.UserDisplayName: Neil Slater
Body: <p>Consider the following problem.</p>
  <p>We have a process, that generates <span class="math-container">$N$</span> stones (e.g. 2000) in one batch <span class="math-container">$b$</span>. Every pebble has state <span class="math-container">$s_{i}^b$</span> and reward <span class="math-container">$s_i^b$</span>. After choosing one pebble <span class="math-container">$i$</span> from the <span class="math-container">$N$</span>, we start sampling again using the chosen pebble as a starting point and we generate the next batch <span class="math-container">$b+1$</span>. The state <span class="math-container">$s_i^b$</span> is a vector of real-values and the reward <span class="math-container">$r_i^b$</span> is a real value.</p>
  <p>The problem is to choose pebbles so that we maximize reward <span class="math-container">$r_i^b$</span> in long term. Because depending on how we choose the pebble, we can sample around the region that gives a better or worse reward <span class="math-container">$r$</span>.</p>
  <p>During each new batch, we make one selection of one pebble (so actions can from <span class="math-container">$i, \dots, N$</span>. We have access to the previous <span class="math-container">$m$</span> batches (e.g. through replay buffer) with their rewards and states.</p>
  <p>In short, it looks like this:</p>
  <ol start="0">
  <li>Chose randomly the first pebble from which we start sample;</li>
  <li>We start sampling from the chosen pebble in the current batch;</li>
  <li>We sample <span class="math-container">$N$</span> pebbles from a process, each pebble have a state <span class="math-container">$s_i^b$</span> and reward <span class="math-container">$r_i^b$</span>;</li>
  <li>We can chose one pebble from <span class="math-container">$i \dots N$</span> as action <span class="math-container">$a_i^b$</span> based on state <span class="math-container">$s_i^b$</span> and reward <span class="math-container">$r_i^b$</span>;</li>
  <li>Go to point 1 and repeat;</li>
  </ol>
  <p>For example, at the moment, I choose in a given batch <span class="math-container">$b$</span> pebble with max reward <span class="math-container">$r_i^b$</span>, so</p>
  <p><span class="math-container">$$i = \underset{i}{\mathrm{argmax}}\, r_i^b$$</span> and then use <span class="math-container">$a_i^b$</span> for a the current batch <span class="math-container">$b$</span>.</p>
  <p>But what I want is to choose:
  <span class="math-container">$$i = \underset{i}{\mathrm{argmax}}\, \underset{b}{E}[R_i^b | s_i, a_i]$$</span></p>
  <p>Graphically speaking:</p>
  <p>Assuming one Batch (N) is 30
  P - pebble, <strong>P</strong> - chosen pebble</p>
  <p>batch 1: PPPPPPPPPPPPPPPPPPPPPPPPPP<strong>P</strong>PPP</p>
  <p>batch 2: PPPPPPPPPPPPP<strong>P</strong>PPPPPPPPPPPPPPPP</p>
  <p>batch 3: PP<strong>P</strong>PPPPPPPPPPPPPPPPPPPPPPPPPPP</p>
  <p>batch 4: PPPPPPPPPPPPPPPPPPPPPPP<strong>P</strong>PPPPPP</p>
  <p>batch 5: PPPPPPPPPPPPPPPPPPPPPPPPPPPP<strong>P</strong>P</p>
  <p>So, if I have a batch <span class="math-container">$N$</span>, when I choose one element from the batch as an action, so the expected reward is the highest in long term, and start the sampling again from it. So only one element per batch can be chosen. And only choice of the one pebble per batch does affect the sequence in the next batch, but not inside the current batch.</p>
  <p>The problem is, what Reinforcement Learning algorithm to use, when we choose only one item from N. And the one choice affect the whole sampled sequence in the next batch. For example in batch 1 to 4, the reward can be very low, and in batch 5 the reward is super high, if we chose wisely the pebbles in 4 previous batchs.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-23T20:25:56.483Z
Comments.Text: Please could you give more details about the environment and the goal of the agent, what you have so far is not clear. For instance it is not clear whether you make one selection for each new batch, and it is not clear whether there is any data that would help the agent select a high reward pebble, or why the state $S_t$ is associated with a choice of pebble (or what that means in terms of predicting next choice, or impact on next state).
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-24T10:50:19.407Z
Comments.Text: @NeilSlater Tried to make it more precise, if you can judge if there's enough information or not, comment please
Comments.UserDisplayName: Daniel Wiczew
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-25T11:31:17.710Z
Comments.Text: In the title, you wrote "continuous action space", but it seems that you have a discrete action space, i.e. one "pebble" (or stone) from some set of $N$ actions (which you call a "batch", which may be confusing). Am I misunderstanding your description or is it a typo?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-25T12:06:21.923Z
Comments.Text: @nbro
  
  Yes, corrected - should be large discrete
Comments.UserDisplayName: Daniel Wiczew
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-25T12:53:49.220Z
Comments.Text: Sorry it is still not very clear. (1) It is not clear whether time steps are same as batches - do you make only one decision per batch. (2) It is not clear what the state means or is used for - most importantly, does selecting a pebble that has a state $s^b_i$ have any impact on the next batch $b+1$? (3) Am I correct in thinking that the action choice is a value of $i$ - i.e. selecting one specific pebble from the batch, and after which there is another time step, with a new batch? However, your step 3 implies that you can select more than one pebble per batch?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-25T12:56:33.213Z
Comments.Text: Also, your objective looks wrong, since it is maximising reward over a single batch - which you can already do by selecting by the reward that you already know. You need to involve time steps here in some way, and to explain how the action choice at one time step influences what happens in later time steps. If there is no control over the sequence based on actions that you take, then you probably do not have a reinforcement learning problem, but you may still have a related problem e.g. k-armed bandit.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-27T09:58:49.493Z
Comments.Text: @NeilSlater
  >If there is no control over the sequence based on actions that you take, then you probably do not have a reinforcement learning problem, but you may still have a related problem e.g. k-armed bandit. 
  I have only control over the point between batches, but not the sequence in the batch. 
  I'll correct the stack in a moment
Comments.UserDisplayName: Daniel Wiczew
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-27T11:24:56.957Z
Comments.Text: Is the information about the impact of your choice of pebble on the next batch encoded into the pebbles state? So far I don't see any purpose for the state value?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-27T12:14:02.603Z
Comments.Text: @NeilSlater
  Yes, it's a real-valued 1xm vector. So during every batch we get a N x m matrix, where N is the batch size.
Comments.UserDisplayName: Daniel Wiczew
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-28T06:24:01.347Z
Comments.Text: There will never be good sample efficiency, it's kind of an oxymoron in RL because dynamics can be arbitrarily sharp and the NN approximater will need to take that into account or be structured in a way which incorporates known dynamics.
Comments.UserDisplayName: FourierFlux
Tags: <reinforcement-learning><deep-rl><sample-efficiency>
Title: Reinforcement Learning method suitable for a large discrete action space with high sample efficiency
UserDisplayName: Daniel Wiczew
ThreadText: # Reinforcement Learning method suitable for a large discrete action space with high sample efficiency
  
  (Asked by: username_0 on 2021-10-23)
  
  Consider the following problem.
  
  We have a process, that generates $N$ stones (e.g. 2000) in one batch $b$. Every pebble has state $s\_{i}^b$ and reward $s\_i^b$. After choosing one pebble $i$ from the $N$, we start sampling again using the chosen pebble as a starting point and we generate the next batch $b+1$. The state $s\_i^b$ is a vector of real-values and the reward $r\_i^b$ is a real value.
  
  The problem is to choose pebbles so that we maximize reward $r\_i^b$ in long term. Because depending on how we choose the pebble, we can sample around the region that gives a better or worse reward $r$.
  
  During each new batch, we make one selection of one pebble (so actions can from $i, \dots, N$. We have access to the previous $m$ batches (e.g. through replay buffer) with their rewards and states.
  
  In short, it looks like this:
  
  0. Chose randomly the first pebble from which we start sample;
  1. We start sampling from the chosen pebble in the current batch;
  2. We sample $N$ pebbles from a process, each pebble have a state $s\_i^b$ and reward $r\_i^b$;
  3. We can chose one pebble from $i \dots N$ as action $a\_i^b$ based on state $s\_i^b$ and reward $r\_i^b$;
  4. Go to point 1 and repeat;
  
  For example, at the moment, I choose in a given batch $b$ pebble with max reward $r\_i^b$, so
  
  $$i = \underset{i}{\mathrm{argmax}}\, r\_i^b$$ and then use $a\_i^b$ for a the current batch $b$.
  
  But what I want is to choose:
  $$i = \underset{i}{\mathrm{argmax}}\, \underset{b}{E}[R\_i^b | s\_i, a\_i]$$
  
  Graphically speaking:
  
  Assuming one Batch (N) is 30
  P - pebble, **P** - chosen pebble
  
  batch 1: PPPPPPPPPPPPPPPPPPPPPPPPPP**P**PPP
  
  batch 2: PPPPPPPPPPPPP**P**PPPPPPPPPPPPPPPP
  
  batch 3: PP**P**PPPPPPPPPPPPPPPPPPPPPPPPPPP
  
  batch 4: PPPPPPPPPPPPPPPPPPPPPPP**P**PPPPPP
  
  batch 5: PPPPPPPPPPPPPPPPPPPPPPPPPPPP**P**P
  
  So, if I have a batch $N$, when I choose one element from the batch as an action, so the expected reward is the highest in long term, and start the sampling again from it. So only one element per batch can be chosen. And only choice of the one pebble per batch does affect the sequence in the next batch, but not inside the current batch.
  
  The problem is, what Reinforcement Learning algorithm to use, when we choose only one item from N. And the one choice affect the whole sampled sequence in the next batch. For example in batch 1 to 4, the reward can be very low, and in batch 5 the reward is super high, if we chose wisely the pebbles in 4 previous batchs.
  
  **Tags:** reinforcement-learning, deep-rl, sample-efficiency
  
  > **Comments:**
  > **username_1**: Please could you give more details about the environment and the goal of the agent, what you have so far is not clear. For instance it is not clear whether you make one selection for each new batch, and it is not clear whether there is any data that would help the agent select a high reward pebble, or why the state $S_t$ is associated with a choice of pebble (or what that means in terms of predicting next choice, or impact on next state).  
  > **username_0**: @username_1 Tried to make it more precise, if you can judge if there's enough information or not, comment please  
  > **username_2**: In the title, you wrote "continuous action space", but it seems that you have a discrete action space, i.e. one "pebble" (or stone) from some set of $N$ actions (which you call a "batch", which may be confusing). Am I misunderstanding your description or is it a typo?  
  > **username_0**: @username_2  Yes, corrected - should be large discrete  
  > **username_1**: Sorry it is still not very clear. (1) It is not clear whether time steps are same as batches - do you make only one decision per batch. (2) It is not clear what the state means or is used for - most importantly, does selecting a pebble that has a state $s^b_i$ have any impact on the next batch $b+1$? (3) Am I correct in thinking that the action choice is a value of $i$ - i.e. selecting one specific pebble from the batch, and after which there is another time step, with a new batch? However, your step 3 implies that you can select more than one pebble per batch?  
  > **username_1**: Also, your objective looks wrong, since it is maximising reward over a single batch - which you can already do by selecting by the reward that you already know. You need to involve time steps here in some way, and to explain how the action choice at one time step influences what happens in later time steps. If there is no control over the sequence based on actions that you take, then you probably do not have a reinforcement learning problem, but you may still have a related problem e.g. k-armed bandit.  
  > **username_0**: @username_1 >If there is no control over the sequence based on actions that you take, then you probably do not have a reinforcement learning problem, but you may still have a related problem e.g. k-armed bandit.  I have only control over the point between batches, but not the sequence in the batch.  I'll correct the stack in a moment  
  > **username_1**: Is the information about the impact of your choice of pebble on the next batch encoded into the pebbles state? So far I don't see any purpose for the state value?  
  > **username_0**: @username_1 Yes, it's a real-valued 1xm vector. So during every batch we get a N x m matrix, where N is the batch size.  
  > **username_3**: There will never be good sample efficiency, it's kind of an oxymoron in RL because dynamics can be arbitrarily sharp and the NN approximater will need to take that into account or be structured in a way which incorporates known dynamics.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-10-27. Score: 1
  
  My understanding of your environment is:
  
  * The batch number $b$ is the same thing as a time step $t$. Each batch is associated with a single static representation of the environment, the agent makes one decision, then receives a reward and a next state. I am using $t$ instead of $b$ to match the usual name seen in RL.
  * There is a *generator* which can be in a state $s\_t$, initially unknown for $s\_0$.
  * Each time step, $t$, the *generator* creates a batch of "pebbles". The generator state $s\_t$ determines the output of the generator, and is the *only* non-random influence on the contents of each batch - it controls the possible rewards plus the possible next states.
  * Selecting a specific pebble from the batch returns an immediate reward $r\_{t+1}$ plus sets the next state $s\_{t+1}$. This is the agent's action, and it can choose any pebble from the batch as its action $a\_t$.
  * The agent can see the values of $r\_{t+1}$ and $s\_{t+1}$ associated with each pebble before making its selection.
  
  This is a slightly unusual setup for an MDP, but I think it is still a valid MDP, and the expected return can still be maximised using reinforcement learning. One important detail is that although you have a discrete list of actions in each batch, the action index values look like they are meaningless. Your action choice is really to choose the next state $s\_{t+1}$ from a presented list of available states. Your action space is therefore continuous, not discrete, even though at each step you are selecting from a discrete set of actions.
  
  The environment design is different enough from standard that most off-the-shelf RL agent libraries will not work for you. However, you can take advantage of this knowledge of the action space, and the fact that there is no other meaningful state than that selected by the agent when it chooses a pebble, to learn state values efficiently.
  
  I would suggest you use a variant of Q-Learning, based on the "afterstate" values that you are selecting. You can train a neural network to approximate the state value function $\hat{v}(s,\theta)$ and you have a choice whether to use discounted returns or an average reward setting. When deciding the greedy target policy, you will want to select according to
  
  $$\pi = \text{argmax}\_i (r\_i + \gamma \hat{v}(s\_i,\theta))$$
  
  for discounted return. For Q learning, technically you should also store the whole batch output in experience replay, because the TD target will be
  
  $$g = \text{max}\_i (r\_i + \gamma \hat{v}(s\_i,\theta))$$
  
  and you won't know what this max will be later at the time of storing the memory. There may be ways around that - for instance you could use SARSA updates based on the actual action taken, or you could store the value of $g$. However, these would be less sample efficient and you would need to discard the memory at a faster rate, before it became too out of date with respect tothe current policy.
  
  I think an average reward will be closer to your stated goal of generating highest expected reward from each individual batch, but I am not 100% certain how to set up the policy for that. Whilst a discounted return may end up preferring a high immediate reward in some circumstances. However, you may be able to get near identical behaviour by setting $\gamma$ high enough (e.g. $0.99$ or higher) in the more familiar discounted return setting.
  
  The efficiency of this approach will depend on how easy it is for the agent to learn the mapping between states and the quality of the next batch. However, you should have a higher sample efficiency when selecting by afterstate, because the agent does not need to learn separately how actions relate to states.
  
  
  ---
  
  