I'm trying to implement Andersen and Broadie's dual method for an upper bound (here) of a regular American Put. I understand the process to compute it, but I have a conceptual issue : everything relies on the computation of an approximation of the Doob's martingale.

This approximation can be computed through Monte-carlo sub-simulations using a stopping rule to determine where to start and stop sub paths. So far, so good. But when looking for the stopping rule for the American Put (there, section 2.3.1), I see that optimal exercises times are defined as the instants when (K-S)+ is above the value of the Put... which seems like going around in circles to me (to compute the put you need the exercise times, to get the exercise times you need the put). So how to concretely proceed ?

(Others use regression to compute the conditional expectations, but since Andersen and Broadie don't, I was wondering whether we could avoid it in this case)

Andersen--Broadie converts an exercise strategy into an upper bound. The better the exercise strategy the better the upper bound. You can get the exercise strategy by using regression to approximate the continuation value and this is pretty standard -- the LS Method is widely used but does have defects.

Once you have an exercise strategy you need the value of the product using that strategy at each exercise time on each path. The only effective way to get this is a sub-simulation which gives a noisy estimate of an unbiased estimate. Regression at this point doesn't give an unbiased estimate so you are not guaranteed an upper bound.