If these are super bright white LEDs, a set of 18 (likely 6 strings of 3 in series or 9 strings of 2 in series if they operate off 5V) is likely to draw on the order of 200-300mA, not the full 500 allowed on a USB port after enumeration. Still, designing for half an amp isn't a huge deal.
Pack voltage spec on Li-Ion batteries is usually at full charge. It'll go down by ~10% before it "falls off a cliff" when the pack is almost fully depleted. So figure you're range here will be about 6.5-7.5V. You want 5V out. This isn't really enough to justify a switch mode regulator. Just use a 7805. Your maximum power dissipation will be (7.4V-5V)*0.5A=1.2W, and you'll be delivering 5V*0.5A=2.5W to the load for an efficiency of ~68%. A cheap buck regulator could attain 80-85% efficiency, so we're not doing too bad with our linear solution, though a high-efficiency design can top 95% at the cost of significant circuit complexity.
Typical drop-out voltage on a 7805 is 2V@1A, but lower at 0.5A out, so we need at least ~6.75V in. That's probably down into the range of near full depletion on the pack.
Free air thermal resistance on a TO-220 LM7805 is 65C/W, and we're dissipating 1.2W (max), so we could expect a worst case temp rise of 65*1.2=78C. That's a bit hot (~100C in a typical room ambient), so a heat sink would be recommended. Note that the regulator is spec'd to 125C, so if you don't mind it being too hot to touch during operation, a heat sink is not strictly required.
You'll be pulling a constant 500mA from the pack irrespective of pack voltage, so expect 4400/500=8.8 hours of battery life if you run it all the way down. In practice, with an older pack and not running it all the way down (hard on the battery), you'll probably get 7-7.5 hours.
If you go switch mode, things change. Much less power is lost in the regulator, and your current draw is non-constant (it will vary as the pack voltage drops). Might be worth it if you want to play around. In a commercial product, I would probably go SMPS here, but on something I'm hacking up to play with, I'd just grab a 7805 from my parts bin.
Make SURE your Li-Ion pack has an internal safety board. DO NOT use it otherwise as there is a MAJOR fire hazard! If it does catch on fire, whatever you do, don't put water on it! Even with an internal safety board, take care not to short circuit the output. Currents in excess of 200A can easily flow before the safety board cuts things off, which could cause injury due to heating or sparking.
Also, how do you plan to recharge this thing?