We consider a wireless system with multiple channels when each channel has several different transmission states. Different states are associated with different probabilities of successful transmissions. In such networks, we are faced with making transmission decisions in the presence of partial information about channel states. This (typically probabilistic) information about any channel can be refined by sending control packets in the channels. In presence of multiple alternative channels, this process of probing every channel to find the best one is onerous and resource consuming. There is a natural tradeoff between the resource consumed in probing and the estimate of channel state we can obtain. The desired tradeoff can be attained by judiciously determining which and how many channels to probe and also which channel to transmit. We present adaptive algorithms for provably approximating the desired tradeoffs within constant factors. © 2006 IEEE.