I was learning about Multi-Armed Bandits (MAB) and came across the so called regret:

$$ R_T(\pi) = \max_{i \in [n]} G_T(i) - G_T(\pi) = \max_{i \in [n] } \sum^T_{t=1} r_{i,t} - \sum^T_{t=1} r_{\pi(t),t} $$

where $\pi$ is the policy nad $r_i,t$ is regret by are $i$ at time step $t$ (note I am trying to follow RL from Sutton & Barto notation to ease comparison).

The (finite horizon) gain in reinforcement learning (RL) is usually:

$$ G_t = \sum^T_{t=1} R_{t+1}$$

when there is no expectation, regret and maximizing gain are the same of course. So in this case my question of "why does MAB not use the same objective as RL" doesn't seem very interesting.

However, when we include expectations, things seem to change (that is my assummptuion, otherwise I don't see why there would be a difference between the objective in MAB and RL). In other words this here is where I assume my confusion stems from. Note that I am aware that there are other sort of objectives like simple regret or guessing the arm with most reward. Those only worry about explorative nature of the problem and I won't consider them (I only care the goal/objective that seems analogous to the usually RL problem).

I tried expanding the expectation:

$$ E[ R_T(\pi) ] = E\left[ \max_{i \in [n]} G_T(i) - G_T(\pi)\right] = E\left[ \max_{i \in [n] } \sum^T_{t=1} r_{i,t} - \sum^T_{t=1} r_{\pi(t),t} \right] $$

I understand that the max function is convex so we get the PseudoRegret $\bar R(\pi)$:

$$ \bar R(\pi)= \max_{i \in [n]} E[ G_T(i) ] - E[ G_T(\pi) ] \leq E\left[ \max_{i \in [n]} G_T(i) - G_T(\pi)\right] = E[ R_T(\pi) ] $$

clearly they are not the same because of the inequality above (i.e. just minimizing the expected sum $E[ G_T(\pi) ]$). Obviously, just minimizing the lower bound to the regret doesn't seem to help optimize the real regret without further analysis (if that were our objective at all). But I don't understand why I'd ever be interested in the regret (clearly Reinforcement doesn't car, I could imagine attempting to define something similar) and not just total rewards I collect after my trajectory (or in expectation to my trajectory). Total sum of expected rewards seems the natural objective to me.

So my questions are:

  • Why do we not minimize some sort of Regret in Reinforcement Learning (RL)? I guess I view MAB just as fixing a state so it doesn't seem that RL should prefer total sums rather than regrets...or at least thats what it seems to me.
  • What is the advantage of including Regret (if it could be optimized directly). What advantages or properties does it have that simply sum of total expected rewards does not have? (note I've been assuming finite horizon and no discount factor).
  • Does regret have properties I am not seeing compared to total sum of rewards?

I just don't appreciate why I should be interested in regret and why RL doesn't seem to even consider it.

note: I do see that PseudoRegret is the same as maximizing the total sum of rewards (or at least it seems to me to be equivalent).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.