  The search for primordial gravitational waves in the Cosmic Microwave
Background (CMB) will soon be limited by our ability to remove the lensing
contamination to $B$-mode polarization. The often-used quadratic estimator for
lensing is known to be suboptimal for surveys that are currently operating and
will continue to become less and less efficient as instrumental noise
decreases. While foregrounds can in principle be mitigated by observing in more
frequency bands, progress in delensing hinges entirely on algorithmic advances.
We demonstrate here a new inference method that solves this problem by sampling
the exact Bayesian posterior of any desired cosmological parameters, of the
gravitational lensing potential, and of the delensed CMB maps, given lensed
temperature and polarization data. We validate the method using simulated CMB
data with non-white noise and masking on up to 650\,deg$^2$ patches of sky. A
unique strength of this approach is the ability to jointly estimate
cosmological parameters which control both the primordial CMB and the lensing
potential, which we demonstrate here for the first time by sampling both the
tensor-to-scalar ratio, $r$, and the amplitude of the lensing potential,
$A_\phi$. The method allows us to perform the most precise check to-date of
several important approximations underlying CMB-S4 $r$ forecasting, and we
confirm these yield the correct expected uncertainty on $r$ to better than 10%.
