A method, apparatus, and manufacture for encoding a video sequence is provided. During a first exploitation phase of an encoding pass of the video encoding, macro-blocks are encoded employing at least one encoding parameter. At least one encoder statistic is evaluated based on the encoding of macro-blocks during the first exploitation phase. Next, during a first exploration phase of the encoding pass, macro-blocks are encoded employing at least one encoding parameter that is different than the encoding parameter(s) used during the first exploitation phase. At least one encoder statistic is evaluated based on the encoding of the macro-blocks during the first exploitation phase. The encoder statistic(s) based on the first exploration stage is compared when the encoder statistic(s) based on the first exploitation phase, and a steady-state value of the encoding parameter(s) is updated based on the comparison. The process may then continue to alternate between exploration and exploitation phases.