In [5], the authors showed that threshold policies solve an optimal flow control problem for discrete-time M|M|1 queues, where the decision-maker seeks to maximize the system throughput subject to a bound on the long-run average queue size. In this paper, attention focuses on a non-Bayesian adaptive version of this problem when the arrival and service rates are assumed to be unknown constants. By invoking the Certainty Equivalence Principle, adaptive threshold policies are generated by substituting maximum likelihood estimates for the rate parameters in the definition of the optimal threshold policies. Under such policies, the maximum likelihood estimates are shown to be strongly consistent through an indirect method of analysis that combines ideas from stochastic ordering, a study of the rates of convergence via the theory of Large Deviations and absolutely continuous changes of measures. The optimality of the adaptive threshold policies follows as a byproduct of this consistency result.