Drug-induced dedifferentiation towards a drug-tolerant persister state is a common mechanism cancer cells exploit to escape therapies, posing a significant obstacle to sustained therapeutic efficacy. The dynamic coordination of epigenomic and transcriptomic programs at the early-stage of drug exposure, which initiates and orchestrates these reversible dedifferentiation events, remains largely unexplored. Here we employ high-temporal-resolution multi-omics profiling, information-theoretic approaches, and dynamic system modeling to probe these processes in BRAF-mutant melanoma models and patient specimens. We uncover a hysteretic transition trajectory of melanoma cells in response to oncogene inhibition and subsequent release, driven by the sequential operation of two tightly coupled transcriptional waves, which orchestrate genome-scale chromatin state reconfiguration. Modeling of the transcriptional wave interactions predicts NF-{kappa}B/RelA-driven chromatin remodeling as the underlying mechanism of cell-state dedifferentiation, a finding we validate experimentally. Our results identify critical RelA-target genes that are epigenetically modulated to drive this process, establishing a quantitative epigenome gauge to measure cell-state plasticity in melanomas, which supports the potential use of drugs targeting epigenetic machineries to potentiate oncogene inhibition. Extending our investigation to other cancer models, we identify oxidative stress-mediated NF-{kappa}B/RelA activation as a common mechanism driving cellular transitions towards drug-tolerant persister states, revealing a novel and pivotal role for the NF-{kappa}B signaling axis in linking cellular oxidative stress to cancer progression.