Bài báo này đề xuất các thuật toán trực tuyến cổ điển và lượng tử mới cho các quy trình quyết định Markov phần thưởng trung bình (MDP) hữu hạn và vô hạn. Thuật toán được đề xuất dựa trên mô hình học tăng cường (RL) kết hợp khám phá-sinh sản, trong đó các tác nhân có thể tự do tương tác với môi trường, đôi khi thông qua lấy mẫu sinh sản (tức là truy cập vào một "trình mô phỏng"). Bằng cách sử dụng cả thuật toán cổ điển và lượng tử để ước tính các chính sách tối ưu trong các mô hình sinh sản, chúng tôi chứng minh rằng bằng cách tính toán trực tiếp và sử dụng các chính sách tối ưu, chúng tôi tránh được một số mô hình RL, chẳng hạn như "lạc quan trong điều kiện bất định" và "lấy mẫu hậu nghiệm", và thu được các giới hạn hối tiếc tốt hơn so với các nghiên cứu trước đây. Đối với các MDP hữu hạn, thuật toán lượng tử thu được một giới hạn hối tiếc chỉ phụ thuộc logarit vào số bước thời gian T, do đó vượt qua giới hạn cổ điển $O(\sqrt{T})$. Điều này phù hợp với sự phụ thuộc thời gian của các nghiên cứu lượng tử trước đây của Ganguly và cộng sự (arXiv'23) và Zhong và cộng sự. (ICML'24), nhưng với sự phụ thuộc được cải thiện vào các tham số khác, chẳng hạn như kích thước không gian trạng thái S và kích thước không gian hành động A. Đối với các MDP chân trời vô hạn, ranh giới cổ điển và lượng tử vẫn duy trì sự phụ thuộc $O(\sqrt{T})$, nhưng có hệ số S và A tốt hơn. Tuy nhiên, chúng tôi đề xuất một phép đo hối tiếc mới cho các MDP chân trời vô hạn, chứng minh rằng các thuật toán lượng tử có hối tiếc $\operatorname{poly}\log{T}$ tốt hơn theo cấp số nhân so với các thuật toán cổ điển. Cuối cùng, chúng tôi tổng quát hóa tất cả các kết quả thành không gian trạng thái compact.
