bandits to cost-sensitive classification, which is highly non-trivial for online learning problems in general (@hazan2016computational). However, the practibility of the above algorithms is heavily restricted due to their reliance on the cost-sensitive classification oracle (\[eq:csc\]), as this task is computationally intractable even for simple policy classes (@klivans2009cryptographic) and typically involves solving NP-hard problems. As a result, the practical implementations of the above classification-oracle-based algorithms typically resort to heuristics (@agarwal2014taming [@foster2018practical; @bietti2018contextual]). Moreover, the above algorithms are memory hungry: since they must feed *augmented* versions of the dataset (rather than the original version of the dataset) into the oracle, they have to repeatedly create auxiliary data and store them in memory. We refer to [@foster2018practical] and [@foster2020beyond] for more detailed descriptions on the drawbacks of these approaches in terms of computational efficiency and practical implementability.

### Realizibility-based Approaches

In contrast to the agnostic setting where research primarily focuses on designing general-purpose algorithms that work for any given $\Pi$, a majority of research in the realizable setting tends to design specialized algorithms that work well for a particular parametrized family of ${{\mathcal{F}}}$. Two of the dominant strategies for the realizable setting are upper confidence bounds (e.g., @filippi2010parametric [@abbasi2011improved; @chu2011contextual; @li2017provably; @li2019nearly]) and 