An adaptive control system for solving a Markov control problem with long-run average cost is presented; here, system transitions and reward structure are unknown. An optimal policy and a corresponding system performance are derived.