In　wireless　mobile　environment,　the　wireless　channels　are　unreliable　and　change　fast　due　to　fading　and　users＇　movement.　Since　the　wireless　channel　state　is　not　directly　observable　at　the　receiver　but　is　embedded　in　the　received　signal,　this　paper　uses　hidden　Markov　model　(HMM)　to　model　and　predict　the　state　of　available　relays,　and　considers　relay　selection　as　a　stochastic　process　where　the　state　of　wireless　channel　varies　randomly.　The　objective　of　the　process　is　to　select　one　relay　among　different　alternatives　in　each　time-slot　according　to　their　channel　state　information　(CSI)　with　the　goal　of　maximizing　the　long　term　information　rate　of　the　whole　transmission　period.　We　model　the　whole　procedure　of　relay　selection　as　a　type　of　partially　observable　Markov　decision　processes　(POMDPs),　and　the　optimal　policy　of　which　relay　will　be　selected　at　each　time-slot　can　be　acquired　by　solving　POMDPs　with　dynamic　programming-based　hidden　Markov　model　scheduling　algorithms.　Simulation　results　are　presented　to　show　the　effectiveness　of　the　proposed　scheme.　©　2011　IEEE.