  The partial monitoring (PM) framework provides a theoretical formulation of
sequential learning problems with incomplete feedback. On each round, a
learning agent plays an action while the environment simultaneously chooses an
outcome. The agent then observes a feedback signal that is only partially
informative about the (unobserved) outcome. The agent leverages the received
feedback signals to select actions that minimize the (unobserved) cumulative
loss. In contextual PM, the outcomes depend on some side information that is
observable by the agent before selecting the action on each round. In this
paper, we consider the contextual and non-contextual PM settings with
stochastic outcomes. We introduce a new class of PM strategies based on the
randomization of deterministic confidence bounds. We also extend regret
guarantees to settings where existing stochastic strategies are not applicable.
Our experiments show that the proposed RandCBP and RandCBPsidestar strategies
have favorable performance against state-of-the-art baselines in multiple PM
games. To advocate for the adoption of the PM framework, we design a use case
on the real-world problem of monitoring the error rate of any deployed
classification system.
