Other Intangible Assets, Net (Schedule of Other Intangible Assets) (Details) - USD ($) $ in Millions		12 Months Ended
		Jan. 28, 2017	Jan. 30, 2016	Jan. 31, 2015
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	$ 143	$ 146
Amortized intangible assets, Accum. amort.	[1]	(123)	(124)
Amortized intangible assets, Net value	[1]	$ 20	22
Amortized intangible assets, Wtd. Avg. Life in Years	[1],[2]	14 years
Other intangible assets, net	[1]	$ 42	45
Other intangible assets impairments			1	$ 4
Lease Acquisition Costs [Member]
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	116	119
Amortized intangible assets, Accum. amort.	[1]	(105)	(107)
Amortized intangible assets, Net value	[1]	$ 11	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	20
Amortized intangible assets, Accum. amort.	[1]	(13)	(12)
Amortized intangible assets, Net value	[1]	$ 7	8
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)	(5)
Amortized intangible assets, Net value	[1]	$ 2	2
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]	$ 22	23
Trademarks and Trade Names [Member]
Intangible Assets by Major Class [Line Items]
Other intangible assets impairments			$ 1

[1] The change 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 28, 2017 and excludes those assets that are fully amortized.

[3] Includes a non-cash impairment charge of $1 million recorded in 2015. This impairment charge is described more fully in Note 3, Impairment and Litigation Charges