  We study model-free reinforcement learning (RL) algorithms in episodic
non-stationary constrained Markov Decision Processes (CMDPs), in which an agent
aims to maximize the expected cumulative reward subject to a cumulative
constraint on the expected utility (cost). In the non-stationary environment,
reward, utility functions, and transition kernels can vary arbitrarily over
time as long as the cumulative variations do not exceed certain variation
budgets. We propose the first model-free, simulator-free RL algorithms with
sublinear regret and zero constraint violation for non-stationary CMDPs in both
tabular and linear function approximation settings with provable performance
guarantees. Our results on regret bound and constraint violation for the
tabular case match the corresponding best results for stationary CMDPs when the
total budget is known. Additionally, we present a general framework for
addressing the well-known challenges associated with analyzing non-stationary
CMDPs, without requiring prior knowledge of the variation budget. We apply the
approach for both tabular and linear approximation settings.
