Other Intangible Assets, Net (Schedule of Other Intangible Assets) (Details) - USD ($) $ in Millions		12 Months Ended
		Jan. 30, 2016	Jan. 31, 2015
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	$ 146	$ 156
Amortized intangible assets, Accum. amort.	[1]	(124)	(132)
Amortized intangible assets, Net value	[1]	$ 22	24
Amortized intangible assets, Wtd. Avg. Life in Years	[1],[2]	13 years 9 months 18 days
Indefinite life intangible assets, Net Value	[1]	$ 23	25
Other intangible assets, net		45	49
Other intangible assets impairments		1	4
Lease Acquisition Costs [Member]
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	119	128
Amortized intangible assets, Accum. amort.	[1]	(107)	(116)
Amortized intangible assets, Net value	[1]	$ 12	12
Amortized intangible assets, Wtd. Avg. Life in Years	[1],[2]	10 years
Trademarks and Trade Names [Member]
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	$ 20	21
Amortized intangible assets, Accum. amort.	[1]	(12)	(12)
Amortized intangible assets, Net value	[1]	$ 8	9
Amortized intangible assets, Wtd. Avg. Life in Years	[1],[2]	20 years
Favorable Leases {Member]
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	$ 7	7
Amortized intangible assets, Accum. amort.	[1]	(5)	(4)
Amortized intangible assets, Net value	[1]	$ 2	3
Amortized intangible assets, Wtd. Avg. Life in Years	[1],[2]	7 years 9 months 18 days
Runners Point Group [Member]
Intangible Assets by Major Class [Line Items]
Indefinite life intangible assets, Net Value	[1],[3]	$ 23	25
Trademarks and Trade Names [Member]
Intangible Assets by Major Class [Line Items]
Other intangible assets impairments		$ 1	$ 1

[1] The movements in the ending balances also reflect the effect of foreign currency fluctuations due primarily to the movements of the euro in relation to the U.S. dollar

[2] The weighted-average useful life is as of January 30, 2016 and excludes those assets that are fully amortized.

[3] Includes non-cash impairment charges of $1 million recorded in both 2015 and 2014. These impairment charges are described more fully in Note 4, Litigation, Impairment and Other Charges