We consider an adaptive finite state controlled Markov chain with partial state information, motivated by a class of replacement problems. We present parameter estimation techniques based on the information available after actions that reset the state to known value are taken. We prove that the parameter estimates converge w.p. 1 to the true (unknown) parameter, under the feedback structure induced by a certainty equivalent adaptive policy. We also show that the adaptive policy is self- optimizing, in a long-run average sense, for any (measurable) sequence of parameter estimates converging w.p. 1 to the true parameter.