This paper analyzes the effect of a dynamic programming algorithm that controls the departure pushback rate at congested airports, with an emphasis on the uncertainty of the underlying processes. The state of the airport at any time includes the number of departures taxiing to the runway, and the number of departures queued at the runway. The state of the airport surface at the start of a time-window is used to calculate the probability distribution of the state at the end of that time-window, accounting for uncertainties in the system. A cost function that penalizes both excessively long as well as empty runway queues is used to determine the optimal pushback rate for that time-window, using dynamic programming. Since the level of uncertainty in the system increases with the length of time-window, the performance of the dynamic programming policy is evaluated, for different lengths of time-window and planning time horizon. Uncertainty in both arrival and departure demand parameters are evaluated in simulation. Case studies of LaGuardia International Airport (LGA) shows that the dynamic programming algorithm can potentially reduce the departure taxi-out time by over 175,000 minutes over a 2-month period, even in the presence of arrival and departure demand uncertainties, and a planning horizon of 45 minutes.