Internal Regret with Partial Monitoring. Calibration-Based Optimal
  Algorithms
  We provide consistent random algorithms for sequential decision under partial
monitoring, i.e. when the decision maker does not observe the outcomes but
receives instead random feedback signals. Those algorithms have no internal
regret in the sense that, on the set of stages where the decision maker chose
his action according to a given law, the average payoff could not have been
improved in average by using any other fixed law.
  They are based on a generalization of calibration, no longer defined in terms
of a Voronoi diagram but instead of a Laguerre diagram (a more general
concept). This allows us to bound, for the first time in this general
framework, the expected average internal -- as well as the usual external --
regret at stage $n$ by $O(n^{-1/3})$, which is known to be optimal.
