La codificación de voz es una tecnología esencial para las comunicaciones celulares digitales, la voz sobre IP y los sistemas de videoconferencia. Durante más de 25 años, el enfoque principal para la codificación de voz en estas aplicaciones ha sido la codificación predictiva lineal basada en bloques mediante análisis y síntesis. Un enfoque alternativo que ha tenido menos éxito es la codificación de voz muestra por muestra mediante árboles. Reformulamos este último enfoque como un problema de aprendizaje por refuerzo multietapa con L pasos de anticipación que incorpora exploración y explotación para adaptar los parámetros del modelo y controlar el proceso de análisis/síntesis de voz de manera muestra por muestra. La minimización del error de reconstrucción espectralmente moldeado a una profundidad finita gestiona la complejidad y sirve como un sustituto efectivo para la evaluación subjetiva general de la calidad y la inteligibilidad de la voz reconstruida. Se estudian y evalúan diferentes políticas de control que intentan excitar persistentemente los estados del sistema y que fomentan la exploración. Los métodos resultantes producen una calidad de voz reconstruida competitiva con los códecs de voz más populares utilizados hoy en día. Esta nueva formulación de aprendizaje por refuerzo proporciona nuevas perspectivas y abre nuevas direcciones para el diseño del sistema y la mejora del rendimiento.