In a recent ruling, FCC has enabled an unlicensed use of the vacated analogue broadcast TV spectrum, called “White Spaces”, provided that the unlicensed devices detect and avoid primary users (remaining TV channels and wireless MICs). The offered frequency space is very wide and has excellent propagation characteristics, hence the ruling offers a huge potential to develop high-quality, cheap and ubiquitous wireless access, and it also poses several novel design challenges (detecting primaries, network asymmetries, channel selections, etc). In this work we focus on the problem of channel and rate selections for white-spaces. We start by presenting measurements using an indoor testbed operating in the 500 to 600MHz band, and demonstrate that the key challenge is handling variable channel quality. The measurements show that there is significant potential benefit from selecting the best channel and adapting the transmission rate while also revealing non-stationary channel characteristics. The proposed learning algorithms are well suited to non-stationary environments and attempt to minimize “regret” with respect to a best or oracle-like algorithm. The novel aspects of the algorithms includes (i) accounting for the cost incurred when switching channels and synchronization costs, (ii) exploiting inherent correlations between the effective throughputs achieved when selecting the same channel but different transmission rates. We further extend the algorithms to account for fairness issues in network scenarios where several users are served by an access point.