Restatement - Share-based Compensation (Details) (USD $) In Millions, unless otherwise specified	3 Months Ended		9 Months Ended			3 Months Ended	9 Months Ended	3 Months Ended	9 Months Ended	0 Months Ended
	Nov. 02, 2013	Oct. 27, 2012	Nov. 02, 2013	Oct. 27, 2012	Feb. 02, 2013	Oct. 27, 2012 As Reported	Oct. 27, 2012 As Reported	Oct. 27, 2012 Restatement adjustment Share-based compensation Adjustment	Oct. 27, 2012 Restatement adjustment Share-based compensation Adjustment	Feb. 02, 2013 Maximum
Term of immature shares										6 months
Impact to share-based compensation expense		$ 2		$ 12
Impact to share-based compensation expense, net of tax		1		7
Consolidated Balance Sheet
Merchandise inventories	1,119	1,078	1,119	1,078	862	1,076	1,076	2	2
Total current assets	1,345	1,389	1,345	1,389	1,044	1,387	1,387	2	2
Deferred income taxes	29	32	29	32	30	18	18	14	14
Total non-current assets	168	184	168	184	173	170	170	14	14
Share-based compensation	21	30	21	30	35			30	30
Income taxes payable	6	6	6	6	37	8	8	(2)	(2)
Total current liabilities	1,043	1,015	1,043	1,015	856	987	987	28	28
Share-based compensation	28	24	28	24	27			24	24
Total long-term liabilities	2,994	3,309	2,994	3,309	3,003	3,285	3,285	24	24
Additional paid-in capital	63	51	63	51	49	61	61	(10)	(10)
Accumulated deficit	(2,238)	(2,464)	(2,238)	(2,464)	(2,359)	(2,438)	(2,438)	(26)	(26)
Total stockholders' deficit	(2,171)	(2,407)	(2,171)	(2,407)	(2,304)	(2,371)	(2,371)	(36)	(36)
Consolidated Statements of Comprehensive Income
Cost of sales and occupancy expense	665	612	1,816	1,736		611	1,730	1	6
Gross profit	453	402	1,199	1,148		403	1,154	(1)	(6)
Selling, general, and administrative expense	309	277	835	787		278	790	(1)	(3)
Share-based compensation expense	4	2	15	9				2	9
Operating income	135	117	334	337		119	349	(2)	(12)
Income before income taxes	90	54	189	148		56	160	(2)	(12)
Provision for income taxes	32	19	68	53		20	58	(1)	(5)
Net income	58	35	121	95		36	102	(1)	(7)
Comprehensive income	58	35	119	95		36	102	(1)	(7)
Operating Activities:
Net income	58	35	121	95		36	102	(1)	(7)
Share-based compensation and other			19	15			4		11
Merchandise inventories			(254)	(233)			(236)		3
Accrued liabilities and other			(21)	(15)			(11)		(4)
Income taxes			(49)	(33)			(27)		(6)
Net cash provided by operating activities			74	13			16		(3)
Repurchase of common stock							(10)		10
Proceeds from stock options exercised							7		(7)
Net cash used in financing activities			$ 20	$ (138)			$ (141)		$ 3