Constrained Markov Decision Processes (CMDPs) formalize sequential\ndecision-making problems whose objective is to minimize a cost function while\nsatisfying constraints on various cost functions. In this paper, we consider\nthe setting of episodic fixed-horizon CMDPs. We propose an online algorithm\nwhich leverages the linear programming formulation of finite-horizon CMDP for\nrepeated optimistic planning to provide a probably approximately correct (PAC)\nguarantee on the number of episodes needed to ensure an $\\epsilon$-optimal\npolicy, i.e., with resulting objective value within $\\epsilon$ of the optimal\nvalue and satisfying the constraints within $\\epsilon$-tolerance, with\nprobability at least $1-\\delta$. The number of episodes needed is shown to be\nof the order\n$\\tilde{\\mathcal{O}}\\big(\\frac{|S||A|C^{2}H^{2}}{\\epsilon^{2}}\\log\\frac{1}{\\delta}\\big)$,\nwhere $C$ is the upper bound on the number of possible successor states for a\nstate-action pair. Therefore, if $C \\ll |S|$, the number of episodes needed\nhave a linear dependence on the state and action space sizes $|S|$ and $|A|$,\nrespectively, and quadratic dependence on the time horizon $H$.\n