How to construct a reward function for a "wait and see" problem

Question

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.

Answer 1

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$.