I don't normally fly regionals but just got back from a trip to DTW from LGA on AA. At both LGA and DTW they went through the boarding area and checked while boarding with the "if it has wheels it is too big" policy. I had a B&R medium statchel (old design) with no wheels and a Timbuk2 bag and had no problems boarding. The B&R fit in the overhead easily and the Timbuk2 under the seat.