Body: <p>I'm reimplementing an <a href="https://web.mit.edu/decima/" rel="nofollow noreferrer">RL paper</a> about learning a job scheduling policy that acts so as to minimize average job completion time. They claim that this is an &quot;input-driven&quot; problem, i.e. much of the variance in rewards is due to the randomness in job arrival sequences, rather than the policy's actions. They deal with this by computing advantages using &quot;input-dependent&quot; baselines. During each training iteration, they have <span class="math-container">$N$</span> rollout workers running in parallel on <em>the same</em> job arrival sequence, and after all the rollouts are collected, time-based baselines are computed as follows:</p>
  <p><span class="math-container">$$b(t) = \frac{1}{N}\sum_{i=1}^N \hat{r}^i(t) \quad \forall t\geq0$$</span></p>
  <p>where <span class="math-container">$\hat{r}^i(t)$</span> is some continuous interpolation (e.g. piecewise linear) of the discounted returns <span class="math-container">$\{r^i_t\}_{t\in\mathcal{T}^i}$</span> at time <span class="math-container">$t$</span> from rollout <span class="math-container">$i$</span>, where <span class="math-container">$\mathcal{T}^i \subset \mathbb{R}$</span> is the set of simulator wall-times of each step in rollout <span class="math-container">$i$</span>. Then, advantages are computed for each rollout as</p>
  <p><span class="math-container">$$A^i_t = r^i_t - b(t) \quad \forall t\in\mathcal{T}^i, \forall i\in[N].$$</span></p>
  <p>Since the baselines are computed only as a function of the current training iteration's job arrival sequence, they claim that the variance problem is eliminated. I think this is an interesting approach, and I haven't seen it elsewhere, though I admit I am very new to RL.</p>
  <p>Once the advantages are computed, they learn from all the data collected in rollouts <span class="math-container">$i=1,\ldots,N$</span> in a single step using REINFORCE, i.e.</p>
  <p><span class="math-container">$$\theta \gets \theta + \alpha \sum_{i=1}^N \sum_{t\in \mathcal{T}^i} A^i_t\nabla_\theta \log \pi_\theta(a^i_t | s^i_t).$$</span></p>
  <p>I am wondering: is <a href="https://en.wikipedia.org/wiki/Proximal_Policy_Optimization" rel="nofollow noreferrer">PPO</a> suitable for this problem? Could it work well using these advantage calculations instead of using a critic network? If not, could a critic network be configured so as to reduce variance in a similar way, i.e. taking into account only the current job sequence? Thanks!</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-20T11:29:14.283Z
Comments.Text: Can you please put your specific question in the title?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-02-20T20:42:56.130Z
Comments.Text: @nbro I've updated the title
Comments.UserDisplayName: Archie Gertsman
Tags: <deep-rl><variance-reduction>
Title: Can PPO be applied when the environment is "input-driven"?
UserDisplayName: Archie Gertsman
ThreadText: # Can PPO be applied when the environment is "input-driven"?
  
  (Asked by: username_0 on 2023-02-15)
  
  I'm reimplementing an [RL paper](https://web.mit.edu/decima/) about learning a job scheduling policy that acts so as to minimize average job completion time. They claim that this is an "input-driven" problem, i.e. much of the variance in rewards is due to the randomness in job arrival sequences, rather than the policy's actions. They deal with this by computing advantages using "input-dependent" baselines. During each training iteration, they have $N$ rollout workers running in parallel on *the same* job arrival sequence, and after all the rollouts are collected, time-based baselines are computed as follows:
  
  $$b(t) = \frac{1}{N}\sum\_{i=1}^N \hat{r}^i(t) \quad \forall t\geq0$$
  
  where $\hat{r}^i(t)$ is some continuous interpolation (e.g. piecewise linear) of the discounted returns $\{r^i\_t\}\_{t\in\mathcal{T}^i}$ at time $t$ from rollout $i$, where $\mathcal{T}^i \subset \mathbb{R}$ is the set of simulator wall-times of each step in rollout $i$. Then, advantages are computed for each rollout as
  
  $$A^i\_t = r^i\_t - b(t) \quad \forall t\in\mathcal{T}^i, \forall i\in[N].$$
  
  Since the baselines are computed only as a function of the current training iteration's job arrival sequence, they claim that the variance problem is eliminated. I think this is an interesting approach, and I haven't seen it elsewhere, though I admit I am very new to RL.
  
  Once the advantages are computed, they learn from all the data collected in rollouts $i=1,\ldots,N$ in a single step using REINFORCE, i.e.
  
  $$\theta \gets \theta + \alpha \sum\_{i=1}^N \sum\_{t\in \mathcal{T}^i} A^i\_t\nabla\_\theta \log \pi\_\theta(a^i\_t | s^i\_t).$$
  
  I am wondering: is [PPO](https://en.wikipedia.org/wiki/Proximal_Policy_Optimization) suitable for this problem? Could it work well using these advantage calculations instead of using a critic network? If not, could a critic network be configured so as to reduce variance in a similar way, i.e. taking into account only the current job sequence? Thanks!
  
  **Tags:** deep-rl, variance-reduction
  > **Comments:**
  > **username_1**: Can you please put your specific question in the title?  
  > **username_0**: @nbro I've updated the title  
  
  ---
  
  ## 0 answers
  
  