Step-up or Step-down regulators for 3.3v

So I am working on a project with a 3.3v arduino that I want to power with AA batteries. I would prefer to use two AA batteries with a step-up regulator to get to 3.3v, but I am using a BT module (RN-42-HID) that requires 3.3v with a +/- 0.3v tolerance.

Should I go for three batteries with a step-down regulator? Why? Which is more efficient (usage time per battery)?

This little regulator regulator can deliver 300 mA and could work with 2 AA batteries.

dlloyd:
This little regulator regulator can deliver 300 mA and could work with 2 AA batteries.

It could also work with three (up to 8 for the crazy people) but I am wondering if it would be better for battery efficiency to have an underpowered power supply and a step-up regulator or an over-powered power supply and a step-down regulator.

Yeah, I guess it would depend on the type of battery, its fully charged voltage and its depletion voltage. Batteries with overall voltage of 12V or higher would only need step down regulators if regulating to a voltage below its depletion voltage. The battery specs should give some useful information.

Or just use a single battery:

Maybe 1 C cell vs 2 AAs?