© 2016 Elsevier B.V.Most of the opportunistic scheduling algorithms in literature assume that full wireless channel state information (CSI) is available for the scheduler. However, in practice obtaining full CSI may introduce a significant overhead. In this paper, we present a learning-based scheduling algorithm which operates with partial CSI under general wireless channel conditions. The proposed algorithm predicts the instantaneous channel rates by employing a Bayesian approach and using Gaussian process regression. It quantifies the uncertainty in the predictions by adopting an entropy measure from information theory and integrates the uncertainty to the decision-making process. It is analytically proven that the proposed algorithm achieves an fraction of the full rate region that can be achieved only when full CSI is available. Numerical analysis conducted for a CDMA based cellular network operating with high data rate (HDR) protocol, demonstrate that the full rate region can be achieved our proposed algorithm by probing less than 50% of all user channels.