We consider an opportunistic spectrum access problem where the time-varying condition of each channel is modeled as an arbitrary finite-state Markov chain. At each instance of time, a (secondary) user probes a subset of channels and collects a certain reward as a function of the states of the probed channels. Each channel has a potentially different state space and statistics, both unknown to the user. The objective is to construct a good online learning algorithm so as to minimize the difference between the user's performance in total rewards and that of using the channels with the highest expected rewards had it known which ones are the best from a priori knowledge of the channel statistics. We view this problem as a {\em restless} multi-armed bandit problem with multiple plays and provide order optimal algorithms. We first prove logarithmic bounds for the {\em rested} multi-armed bandit problem and then develop an algorithm which utilizes regenerative cycles of a Markov chain and computes a sample-mean based index policy, and show that under mild conditions on the state transition probabilities of the Markov chains this algorithm achieves logarithmic regret uniformly over time, and that this regret bound is also optimal.  
