For valuation of Variable Annuity(VA) contracts with a dynamic hedging program using Monte Carlo methods, nested simulation is often required. The process is computationally challenging in many practical applications. We propose a simulation procedure for estimating the Conditional Tail Expectation (CTE) of liabilities of a VA dynamic hedging strategy. In a CTE calculation, tail scenarios, i.e., the scenarios that result in extreme losses, are most relevant. Thus, correctly identifying those scenarios would greatly improve the efficiency in a nested simulation. The proposed procedure takes advantage of the special structure of the CTE by first identifying a small set of potential tail scenarios from the first tier of simulation. We then focus the simulation budget on only those scenarios. We conduct extensive numerical experiments on different guarantee types and different stock return dynamics.The numerical results show considerably improved accuracy under fixed simulation budget.