This paper presents new algorithms for reinforcement learning and proves that they achieve near-optimal performance in polynomial time for general Markov decision processes (MDPs). The key insight is that the number of actions required to approach the optimal return is lower bounded by the mixing time T of the optimal policy (in the undiscounted case) or the horizon time T (in the discounted case). The algorithms require a number of actions and total computation time that are polynomial in T and the number of states and actions, for both cases. The algorithms explicitly handle the exploration-exploitation trade-off. The paper first discusses the challenges of reinforcement learning, including the trade-off between exploration and exploitation. It then presents results on asymptotic convergence of reinforcement learning algorithms, which do not provide guarantees on the number of actions or computation time required to achieve near-optimal performance. The paper then introduces non-asymptotic results for restricted classes of MDPs and discusses the implications of these results. The main contribution of the paper is the development of new algorithms for reinforcement learning that achieve near-optimal performance in polynomial time for general MDPs. The algorithms are based on the concept of known states, which are states that have been visited sufficiently many times to ensure that the estimated transition probabilities and payoffs are close to their true values. The algorithms use these known states to simulate the MDP and perform value iteration to find optimal policies. The paper also introduces the concept of the "explore or exploit" lemma, which states that either there exists a policy that achieves near-optimal return in the MDP or there exists a policy that allows rapid exploration of unknown states. The algorithms use this lemma to ensure that they either find a near-optimal policy or improve the statistics of unknown states. The paper concludes with a discussion of the implications of the results and the potential for future work. The algorithms are shown to achieve near-optimal performance in polynomial time for both the undiscounted and discounted cases, and they explicitly handle the exploration-exploitation trade-off. The results are significant because they provide the first provably finite-time convergence results for reinforcement learning in general MDPs.This paper presents new algorithms for reinforcement learning and proves that they achieve near-optimal performance in polynomial time for general Markov decision processes (MDPs). The key insight is that the number of actions required to approach the optimal return is lower bounded by the mixing time T of the optimal policy (in the undiscounted case) or the horizon time T (in the discounted case). The algorithms require a number of actions and total computation time that are polynomial in T and the number of states and actions, for both cases. The algorithms explicitly handle the exploration-exploitation trade-off. The paper first discusses the challenges of reinforcement learning, including the trade-off between exploration and exploitation. It then presents results on asymptotic convergence of reinforcement learning algorithms, which do not provide guarantees on the number of actions or computation time required to achieve near-optimal performance. The paper then introduces non-asymptotic results for restricted classes of MDPs and discusses the implications of these results. The main contribution of the paper is the development of new algorithms for reinforcement learning that achieve near-optimal performance in polynomial time for general MDPs. The algorithms are based on the concept of known states, which are states that have been visited sufficiently many times to ensure that the estimated transition probabilities and payoffs are close to their true values. The algorithms use these known states to simulate the MDP and perform value iteration to find optimal policies. The paper also introduces the concept of the "explore or exploit" lemma, which states that either there exists a policy that achieves near-optimal return in the MDP or there exists a policy that allows rapid exploration of unknown states. The algorithms use this lemma to ensure that they either find a near-optimal policy or improve the statistics of unknown states. The paper concludes with a discussion of the implications of the results and the potential for future work. The algorithms are shown to achieve near-optimal performance in polynomial time for both the undiscounted and discounted cases, and they explicitly handle the exploration-exploitation trade-off. The results are significant because they provide the first provably finite-time convergence results for reinforcement learning in general MDPs.