Related Party Transactions (Details) (USD $) In Millions, except Share data, unless otherwise specified	3 Months Ended		9 Months Ended
	Oct. 27, 2012	Oct. 29, 2011	Oct. 27, 2012	Oct. 29, 2011	Jan. 28, 2012
Related Party Transactions
Expenses recognized	$ 3	$ 3	$ 10	$ 10
Long-term debt held	3,368	3,511	3,368	3,511	3,490
Senior secured term loan
Related Party Transactions
Long-term debt held	1,787	1,996	1,787	1,996	1,996
Bain Capital Partners, LLC and The Blackstone Group
Related Party Transactions
Annual management fees			12
Bain Capital Partners, LLC | Printing of circular advertisement services received from an external vendor
Related Party Transactions
Expenses recognized				6
Bain Capital Partners, LLC | Print procurement services received from an external vendor
Related Party Transactions
Expenses recognized	1	1	3	3
The Blackstone Group | Store inventory counting services received from an external vendor
Related Party Transactions
Expenses recognized	2	2	6	6
The Blackstone Group | Candy-type items in stores received from an external vendor
Related Party Transactions
Expenses recognized	5	4	16	13
The Blackstone Group | Lease services of certain properties from a vendor
Related Party Transactions
Expenses recognized	1	1	3	2
The Blackstone Group | Hospitality Services
Related Party Transactions
Expenses recognized	1	1	1	1
Highfields Capital Management LP
Related Party Transactions
Annual management fees			1
Officers no longer with the company
Related Party Transactions
Number of shares repurchased	9,333	17,333	14,667	192,001
Current directors (other than Jill A. Greenthal) | The Blackstone Group | Senior secured term loan
Related Party Transactions
Long-term debt held	$ 51		$ 51