Traditional classification rules offer single-label predictions without confidence levels, which can be problematic in critical domains. In contrast, set-valued classification yields cautious decisions by reporting a set of possible labels to handle the inherited uncertainties in ambiguous instances. Nevertheless, existing set-valued classification methods have two main practical limitations: (1) they neglect the possibility of the emergence of a new class that never appeared in history, and (2) they highly rely on the clearly labeled instances to achieve certain confidence guarantee, which is not the case in online learning with bandit feedback setting such as video recommendations. To address these two challenges, this dissertation is structured into two parts accordingly: we generalize a set-valued classifier to one with the capacity of Out-of-distribution (OOD) detection and design efficient implementations such that a set-valued classifier can be adaptive to the online setting with bandit feedback. In the first part, we introduce the Generalized Prediction Set (GPS) to tackle the OOD detection task with a theoretical guarantee. However, GPS's reliance on computationally intensive quadratic programming limits its scalability. Thus, we propose the Deep Generalized Prediction Set (DeepGPS) method by fusing the deep neural network and a kernel machine, which scales better and provides improved performance on both OOD detection and informative prediction. In the second part, we propose Bandit Class-specific Conformal Prediction (BCCP) in bandit feedback settings, which achieves the set-valued prediction by utilizing an unbiased estimation for the ground truth. To overcome its shortcomings in OOD detection tasks, we introduce the Bandit Generalized Prediction Set (BanditGPS) by incorporating the idea from BCCP and the first works in this dissertation. The algorithms designed in both approaches lead to a $\mathcal{O}(T^{-1/2})$ convergence rate in regret analysis and prediction error control.