Why using regret in online learning

Regret analysis is broadly adopted in learning with online interactions. However, why using regret minimization instead of cost minimization as in other learning tasks such as batch learning? In this short note, we will give an example that by minimizing the regret, the learner gets a better reward.

1.Worst-case cost and worst-case regret cost

Consider the function $g$ defined as $g\left(x\right)\triangleq \underset{y}{max.}f(x,y)$, where $f$ is an arbitrary function. The optimization problem defined as

can be viewed as a worst-case optimization problem, and $g\left(x\right)$ is called worst-case cost.

Let's consider a scenario where we have $f(x,y)$ that represents the time required to drive a car from one location to another given policy $x$ and environment $y$. In this context, $x$ represents the driver's driving pattern, which encompass decisions like adjusting speed, selecting lanes (left or right), and other driving strategies. On the other hand, $y$ represents a binary condition indicating whether it's currently raining ($y=1$) or not ($y=0$). Together, this function captures how the driver's decisions and weather conditions collectively impact the time it takes for the journey.

It's a widely acknowledged fact that driving takes more time on days when it's raining. Thus, $\underset{y}{max.}f(x,y)=f(x,1)$. By definition, the function $g\left(x\right)$ currently represents the time required for driving on rainy days.

Now, define $g^{\text{'}}\left(x\right)\triangleq \underset{y}{max}(f(x,y)-\underset{x^{\text{'}}}{min}f(x^{\text{'}},y))$. We call $g^{\text{'}}\left(x\right)$ the worst-case regret cost. Unlike worst-case cost, the regret cost measures the maximum achievement it can be improved in the past days. For example, if a driver cannot drive in the rainy day due to rheumatoid arthritis. Then there is no difference between $f(x,\mathrm{rain})$ and $f(x^{\text{'}},\mathrm{rain})$ for any $x$ and $x^{\text{'}}$, which makes $g^{\text{'}}\left(x\right)=0$. No regret at all! Because nothing can be improved in the worst-case.

2.An example that minimizes regret cost results in a better policy

Consider the function $f(x,y)$ as follows:

The worst-case cost $g\left(x\right)$ in this example is $\underset{y}{max}.f(x,y)=f(x,0)=100$ for any $x$. Thus,

But for the worst-case regret cost, $g^{\text{'}}\left(0\right)=0$ and $g^{\text{'}}\left(1\right)=99$. Thus

3.Data correlation

The fundamental assumption of standard offline machine learning is that the collected data are independently and identically distributed, stemming from an unknown distribution [2]. However, this assumption can be easily compromised in the realm of online learning [1]. For instance, let's reconsider a scenario involving a driver who refrains from driving on rainy days. In this case, data points (representing the time taken to travel between places) within a one-hour time-frame might have a probability of collection as low as $0$. Conversely, data points beyond one hour might possess a probability of collection greater than $0$. This implies that data collected on different dates adhere to distinct distributions. This distinction underscores a crucial difference between traditional offline learning and online learning.

Bibliography