Answers.Body: <p>In general, the term of art for this problem is &quot;early classification.&quot;</p>
  <blockquote>
  <p>Early classification of time series has been extensively studied for minimizing class prediction delay in time-sensitive applications such as medical diagnostic and industrial process monitoring. A primary task of an early classification approach is to classify an incomplete time series as soon as possible with some desired level of accuracy.</p>
  </blockquote>
  <p>from Gupta, Ashish, et al. &quot;Approaches and applications of early classification of time series: A review.&quot; <em>IEEE Transactions on Artificial Intelligence</em> 1.1 (2020): 47-61.</p>
  <p>Most methods to solve early classification tasks are not specifically about reinforcement learning, but some researchers have posed the early classification problem as a reinforcement learning task. Here's an example:</p>
  <p>In C. Martinez, G. Perrin, E. Ramasso and M. Rombaut, &quot;A Deep Reinforcement Learning Approach for Early Classification of Time Series,&quot; (2018 26th <em>European Signal Processing Conference</em> (EUSIPCO), 2018, pp. 2030-2034, doi: 10.23919/EUSIPCO.2018.8553544) the authors define the reward <span class="math-container">$R$</span> as a function of the action <span class="math-container">$a_t$</span>, the partial sequence <span class="math-container">$S_{:t}$</span> and <span class="math-container">$l$</span> the correct label:
  <span class="math-container">$$
  R(a_t, S_{:t}, l) = \begin{cases}
  1,  &amp; \text{if $a_t$ is the correct label} \\
  -1,  &amp; \text{if $a_t$ is not the correct label &amp; not wait} \\
  - \lambda t^p, &amp; \text{if $a_t$ is wait}
  \end{cases}
  $$</span></p>
  <p>where <span class="math-container">$\lambda$</span> is a tuning parameter that encourages earliness in the predictions and <span class="math-container">$p \ge 0$</span> allows one to change the penalty with time <span class="math-container">$t$</span>. So it appears that your proposed reward is a specific example of the reward outlined in the Martinez paper, with <span class="math-container">$\lambda = 1$</span> and <span class="math-container">$p=0$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-27T19:12:53.980Z
Answers.LastActivityDate: 2022-04-28T03:43:52.417Z
Answers.LastEditDate: 2022-04-28T03:43:52.417Z
Answers.UserDisplayName: Sycorax
Body: <p>I'm working on a problem that I think could probably be represented as a reinforcement learning task, but I'm uncertain about how to design the reward function. The core task is essentially a classification problem, but the data used to make the classification arrives over time. So we want to balance two competing aims:</p>
  <ul>
  <li><p>On the one hand, we want to apply the correct label to the widget quickly.</p>
  </li>
  <li><p>On the other hand, we don't want to apply a label to the widget prematurely.</p>
  </li>
  </ul>
  <p>The widget's true label doesn't change with time -- it's fixed for all time-steps.</p>
  <p>This is how the process works. At each time step, we collect the same set of features about a widget. Then, using the history of observed features, I want the agent to either apply a label to the widget, or else wait for more data. We want the agent to dynamically decide in time what the object's label is. The whole history of current and previously observed features is available to the agent, so the data for a single instance at time <span class="math-container">$t$</span> looks like</p>
  <p><span class="math-container">$$
  x_{1t}, x_{2t}, x_{3t}, \dots, x_{kt}
  $$</span></p>
  <p>and the collection of all time steps up to time <span class="math-container">$T$</span> is a <span class="math-container">$k \times T$</span> matrix of the <span class="math-container">$T$</span> feature vectors.</p>
  <p>My questions are</p>
  <ol>
  <li><p>Does this kind of reinforcement learning task have a specific term of art?</p>
  </li>
  <li><p>How should the reward function be constructed?</p>
  </li>
  </ol>
  <p>My thinking so far is that we could use an approach similar to a maze-solving RL agent, where each &quot;wait&quot; action has a <span class="math-container">$-1$</span> reward, applying the correct label has a <span class="math-container">$+1$</span> reward, and applying an incorrect label has a <span class="math-container">$-1$</span> reward, but this seems rather simplistic. I'm worried that since an incorrect label is the same as waiting, the agent might learn to just guess at random, hoping to get a correct label by chance, instead of learning when to wait for more information.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-04-27T08:38:41.583Z
Comments.Text: You could look into prediction rewards for some ideas. See for example [Satsangi et al. "Maximizing Information Gain in Partially Observable Environments via Prediction Rewards"](https://yashz.github.io/papers/DanPaper-aamas20.pdf).
Comments.UserDisplayName: mikkola
Tags: <reinforcement-learning><reference-request><terminology><reward-functions><reward-design>
Title: How to construct a reward function for a "wait and see" problem
UserDisplayName: user336650
ThreadText: # How to construct a reward function for a "wait and see" problem
  
  (Asked by: username_0 on 2022-04-26)
  
  I'm working on a problem that I think could probably be represented as a reinforcement learning task, but I'm uncertain about how to design the reward function. The core task is essentially a classification problem, but the data used to make the classification arrives over time. So we want to balance two competing aims:
  
  * On the one hand, we want to apply the correct label to the widget quickly.
  * On the other hand, we don't want to apply a label to the widget prematurely.
  
  The widget's true label doesn't change with time -- it's fixed for all time-steps.
  
  This is how the process works. At each time step, we collect the same set of features about a widget. Then, using the history of observed features, I want the agent to either apply a label to the widget, or else wait for more data. We want the agent to dynamically decide in time what the object's label is. The whole history of current and previously observed features is available to the agent, so the data for a single instance at time $t$ looks like
  
  $$
  x\_{1t}, x\_{2t}, x\_{3t}, \dots, x\_{kt}
  $$
  
  and the collection of all time steps up to time $T$ is a $k \times T$ matrix of the $T$ feature vectors.
  
  My questions are
  
  1. Does this kind of reinforcement learning task have a specific term of art?
  2. How should the reward function be constructed?
  
  My thinking so far is that we could use an approach similar to a maze-solving RL agent, where each "wait" action has a $-1$ reward, applying the correct label has a $+1$ reward, and applying an incorrect label has a $-1$ reward, but this seems rather simplistic. I'm worried that since an incorrect label is the same as waiting, the agent might learn to just guess at random, hoping to get a correct label by chance, instead of learning when to wait for more information.
  
  **Tags:** reinforcement-learning, reference-request, terminology, reward-functions, reward-design
  > **Comments:**
  > **username_1**: You could look into prediction rewards for some ideas. See for example [Satsangi et al. "Maximizing Information Gain in Partially Observable Environments via Prediction Rewards"](https://yashz.github.io/papers/DanPaper-aamas20.pdf).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-04-27. Score: 2
  
  In general, the term of art for this problem is "early classification."
  
  > Early classification of time series has been extensively studied for minimizing class prediction delay in time-sensitive applications such as medical diagnostic and industrial process monitoring. A primary task of an early classification approach is to classify an incomplete time series as soon as possible with some desired level of accuracy.
  
  from Gupta, Ashish, et al. "Approaches and applications of early classification of time series: A review." *IEEE Transactions on Artificial Intelligence* 1.1 (2020): 47-61.
  
  Most methods to solve early classification tasks are not specifically about reinforcement learning, but some researchers have posed the early classification problem as a reinforcement learning task. Here's an example:
  
  In C. Martinez, G. Perrin, E. Ramasso and M. Rombaut, "A Deep Reinforcement Learning Approach for Early Classification of Time Series," (2018 26th *European Signal Processing Conference* (EUSIPCO), 2018, pp. 2030-2034, doi: 10.23919/EUSIPCO.2018.8553544) the authors define the reward $R$ as a function of the action $a\_t$, the partial sequence $S\_{:t}$ and $l$ the correct label:
  $$
  R(a\_t, S\_{:t}, l) = \begin{cases}
  1, & \text{if $a\_t$ is the correct label} \\
  -1, & \text{if $a\_t$ is not the correct label & not wait} \\
  - \lambda t^p, & \text{if $a\_t$ is wait}
  \end{cases}
  $$
  
  where $\lambda$ is a tuning parameter that encourages earliness in the predictions and $p \ge 0$ allows one to change the penalty with time $t$. So it appears that your proposed reward is a specific example of the reward outlined in the Martinez paper, with $\lambda = 1$ and $p=0$.
  
  
  ---
  
  