This project proposes transformative research approaches to provide a significant leap toward genuine autonomous cyber defense by enabling playbooks to be dynamically adaptive, predictive, adversary-aware, and trustworthy. Our proposed techniques address the above challenges and enable advancing the science and engineering of the state-of-the-art of intrusion response automation by ambitiously seeking to develop autonomous cyber defense systems that require no or minimal human involvement in the decision-making loop while maximizing effectiveness (i.e., system convergence to a good state) and minimizing the time-to-respond or mitigate. We propose to make cybersecurity autonomous by designing formal models and techniques that can automatically observe, reason, predict, adapt, and act to respond to attacks proactively, providing provable guarantees of safety and convergence.