Answers.Body: <p>I think the key to your problem may not the <strong>one-round</strong>. Use RL to solve the knapsack problem is great related to the topic <strong>rl for combination optimization</strong>. U can use <a href="https://arxiv.org/pdf/1611.09940.pdf" rel="nofollow noreferrer">NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING</a> to get some idea and find more related solutions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T14:57:07.447Z
Answers.LastActivityDate: 2020-04-29T14:57:07.447Z
Answers.UserDisplayName: Jarvis
Answers.Body: <p>This seems like a multi-armed bandit problem (no states involved here). I had the same problem some times ago and I was advised to sample the output distribution M times, calculate the rewards and then feed them to the agent, this was also explained in <a href="https://arxiv.org/pdf/1801.07365.pdf" rel="nofollow noreferrer">this paper</a> Algorithm 1 page 3 (but different problem &amp; different context). I honestly don't know if this will work for your case. You could also take a look at <a href="https://github.com/shshemi/NeuralKnapsack/blob/master/neural_knapsack.py" rel="nofollow noreferrer">this example</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T15:22:32.970Z
Answers.Text: The multi-armed bandit problem seems very different from my problem except for the statelessness. The Neural knapsack seems relevant, but it's under a pay wall
Answers.UserDisplayName: Gilad Deutsch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T20:36:06.493Z
Answers.Text: sorry, what do you mean ?
Answers.UserDisplayName: Habib-Allah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-30T10:06:16.483Z
Answers.Text: What do I mean where?
Answers.UserDisplayName: Gilad Deutsch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-30T12:35:40.717Z
Answers.Text: "but it's under a pay wall" ?
Answers.UserDisplayName: Habib-Allah
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T12:15:41.957Z
Answers.LastActivityDate: 2020-04-29T12:15:41.957Z
Answers.UserDisplayName: Habib-Allah
Answers.Body: <p>You should look into <a href="https://en.wikipedia.org/wiki/Multi-armed_bandit#Contextual_bandit" rel="nofollow noreferrer">contextual bandits</a>, and specifically <a href="https://towardsdatascience.com/13-solutions-to-multi-arm-bandit-problem-for-non-mathematicians-1b88b4c0b3fc" rel="nofollow noreferrer">gradient bandit solvers</a> (see section 13).</p>
  
  <p>Your derivation of the gradient seems correct to me. Instead of a sampled/bootstrapped value function (as in Actor-Critic) or sampled full return (in REINFORCE) you can use the sampled reward. You will probably want to subtract a baseline from <span class="math-container">$v$</span>, e.g. a rolling average reward for the current policy.</p>
  
  <p>I have <a href="https://www.kaggle.com/slobo777/pytorch-giant-gradient-bandit" rel="nofollow noreferrer">successfully used a gradient bandit solver for one-shot optimisation problem</a> with 5000 dimension actions. It was not as strong as a custom optimiser or SAT solver, but whether or not that is an issue for you will depend on the problem.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T12:21:12.647Z
Answers.LastActivityDate: 2020-04-29T12:37:55.323Z
Answers.LastEditDate: 2020-04-29T12:37:55.323Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Besides contextual Bandit or multi-armed Bandit perspective, if you want to use a dataset to train RL policy, I would recommend you <a href="http://tgabel.de/cms/fileadmin/user_upload/documents/Lange_Gabel_EtAl_RL-Book-12.pdf" rel="nofollow noreferrer">Batch RL</a>, it is another RL working in a supervised learning way to train a policy.</p>
  
  <p>For your problem, I think you can still use one-state trajectories to train REINFORCE. For example, there is a trajectory, <span class="math-container">$\tau={(s, a, r, s^{\prime})}$</span>, there <span class="math-container">$s^{\prime}$</span> is NULL. By using REINFORCE, you can get the gradient <span class="math-container">$\theta = \theta + \alpha \nabla_{\theta}log \pi_{\theta}(a|s)r$</span>, and you do not need <span class="math-container">$s^{\prime}$</span> here.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T12:40:41.360Z
Answers.LastActivityDate: 2020-04-29T12:46:19.693Z
Answers.LastEditDate: 2020-04-29T12:46:19.693Z
Answers.UserDisplayName: GoingMyWay
Body: <p>I'm interested about using Reinforcement Learning in a setting that might seem more suitable for Supervised Learning. There's a dataset <span class="math-container">$X$</span> and for each sample <span class="math-container">$x$</span> some decision needs to be made. Supervised Learning can't be used since there aren't any algorithms to solve or approximate the problem (so I can't solve it on the dataset) but for a given decision it's very easy to decide how good it is (define a reward). </p>
  
  <p>For example, you can think about the knapsack problem - let's say we have a dataset where each sample <span class="math-container">$x$</span> is a list (of let's say size 5) of objects each associated with a weight and a value and we want to decide which objects to choose (of course you can solve the knapsack problem for lists of size 5, but let's imagine that you can't). For each solution the reward is the value of the chosen objects (and if the weight exceeds the allowed weight then the reward is 0 or something). So, we let an agent "play" with each sample <span class="math-container">$M$</span> times, where play just means choosing some subset and training with the given value. </p>
  
  <p>For the <span class="math-container">$i$</span>-th sample the step can be adjusted to be:
  <span class="math-container">$$\theta = \theta + \alpha \nabla_{\theta}log \pi_{\theta}(a|x^i)v$$</span> 
  for each "game" with "action" <span class="math-container">$a$</span> and value <span class="math-container">$v$</span>.</p>
  
  <p>instead of the original step:
  <span class="math-container">$$\theta = \theta + \alpha \nabla_{\theta}log \pi_{\theta}(a_t|s_t)v_t$$</span>
  Essentially, we replace the state with the sample.</p>
  
  <p>The issue with this is that REINFORCE assumes that an action also leads to some new state where here it is not the case. Anyway, do you think something like this could work?</p>
  
Tags: <deep-learning><reinforcement-learning>
Title: Reinforcement Learning (and specifically REINFORCE algorithm) for one-round "games"
UserDisplayName: Gilad Deutsch
ThreadText: # Reinforcement Learning (and specifically REINFORCE algorithm) for one-round "games"
  
  (Asked by: username_0 on 2020-04-29)
  
  I'm interested about using Reinforcement Learning in a setting that might seem more suitable for Supervised Learning. There's a dataset $X$ and for each sample $x$ some decision needs to be made. Supervised Learning can't be used since there aren't any algorithms to solve or approximate the problem (so I can't solve it on the dataset) but for a given decision it's very easy to decide how good it is (define a reward).
  
  For example, you can think about the knapsack problem - let's say we have a dataset where each sample $x$ is a list (of let's say size 5) of objects each associated with a weight and a value and we want to decide which objects to choose (of course you can solve the knapsack problem for lists of size 5, but let's imagine that you can't). For each solution the reward is the value of the chosen objects (and if the weight exceeds the allowed weight then the reward is 0 or something). So, we let an agent "play" with each sample $M$ times, where play just means choosing some subset and training with the given value.
  
  For the $i$-th sample the step can be adjusted to be:
  $$\theta = \theta + \alpha \nabla\_{\theta}log \pi\_{\theta}(a|x^i)v$$
  for each "game" with "action" $a$ and value $v$.
  
  instead of the original step:
  $$\theta = \theta + \alpha \nabla\_{\theta}log \pi\_{\theta}(a\_t|s\_t)v\_t$$
  Essentially, we replace the state with the sample.
  
  The issue with this is that REINFORCE assumes that an action also leads to some new state where here it is not the case. Anyway, do you think something like this could work?
  
  **Tags:** deep-learning, reinforcement-learning
  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_1 on 2020-04-29. Score: 1
  
  I think the key to your problem may not the **one-round**. Use RL to solve the knapsack problem is great related to the topic **rl for combination optimization**. U can use [NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING](https://arxiv.org/pdf/1611.09940.pdf) to get some idea and find more related solutions.
  
  
  ---
  
  ### Answer by username_2 on 2020-04-29. Score: 1
  
  This seems like a multi-armed bandit problem (no states involved here). I had the same problem some times ago and I was advised to sample the output distribution M times, calculate the rewards and then feed them to the agent, this was also explained in [this paper](https://arxiv.org/pdf/1801.07365.pdf) Algorithm 1 page 3 (but different problem & different context). I honestly don't know if this will work for your case. You could also take a look at [this example](https://github.com/shshemi/NeuralKnapsack/blob/master/neural_knapsack.py).
  
  > **Comments:**
  > **username_0**: The multi-armed bandit problem seems very different from my problem except for the statelessness. The Neural knapsack seems relevant, but it's under a pay wall  
  > **username_2**: sorry, what do you mean ?  
  > **username_0**: What do I mean where?  
  > **username_2**: "but it's under a pay wall" ?  
  
  ---
  
  ### Answer by username_3 on 2020-04-29. Score: 0
  
  You should look into [contextual bandits](https://en.wikipedia.org/wiki/Multi-armed_bandit#Contextual_bandit), and specifically [gradient bandit solvers](https://towardsdatascience.com/13-solutions-to-multi-arm-bandit-problem-for-non-mathematicians-1b88b4c0b3fc) (see section 13).
  
  Your derivation of the gradient seems correct to me. Instead of a sampled/bootstrapped value function (as in Actor-Critic) or sampled full return (in REINFORCE) you can use the sampled reward. You will probably want to subtract a baseline from $v$, e.g. a rolling average reward for the current policy.
  
  I have [successfully used a gradient bandit solver for one-shot optimisation problem](https://www.kaggle.com/slobo777/pytorch-giant-gradient-bandit) with 5000 dimension actions. It was not as strong as a custom optimiser or SAT solver, but whether or not that is an issue for you will depend on the problem.
  
  
  ---
  
  ### Answer by username_4 on 2020-04-29. Score: 0
  
  Besides contextual Bandit or multi-armed Bandit perspective, if you want to use a dataset to train RL policy, I would recommend you [Batch RL](http://tgabel.de/cms/fileadmin/user_upload/documents/Lange_Gabel_EtAl_RL-Book-12.pdf), it is another RL working in a supervised learning way to train a policy.
  
  For your problem, I think you can still use one-state trajectories to train REINFORCE. For example, there is a trajectory, $\tau={(s, a, r, s^{\prime})}$, there $s^{\prime}$ is NULL. By using REINFORCE, you can get the gradient $\theta = \theta + \alpha \nabla\_{\theta}log \pi\_{\theta}(a|s)r$, and you do not need $s^{\prime}$ here.
  
  
  ---
  
  