Related Party Transactions (Details) (USD $) In Millions, unless otherwise specified	3 Months Ended
	May 04, 2013	Apr. 28, 2012	Feb. 02, 2013
Related Party Transactions
Expenses recognized	$ 4	$ 3
Long-term debt held	3,085	3,490	3,041
Bain Capital Partners, LLC | Print procurement services received from an external vendor
Related Party Transactions
Expenses recognized	1	2
The Blackstone Group | Senior secured term loan
Related Party Transactions
Long-term debt held	34
The Blackstone Group | Lease services of certain properties from a vendor
Related Party Transactions
Expenses recognized	1	1
The Blackstone Group | Store inventory counting services received from an external vendor
Related Party Transactions
Expenses recognized	1	2
The Blackstone Group | Candy-type items in stores received from an external vendor
Related Party Transactions
Expenses recognized	6	5
The Sponsors
Related Party Transactions
Annual management fees	12
Highfields Capital Management LP
Related Party Transactions
Annual management fees	$ 1