Other Intangible Assets, Net (Schedule of Other Intangible Assets) (Details) - USD ($) $ in Millions		Apr. 29, 2017	Jan. 28, 2017	Apr. 30, 2016
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	$ 145	$ 143	$ 151
Amortized intangible assets, Accum. amort.	[1]	(125)	(123)	(129)
Amortized intangible assets, Net value	[1]	20	20	22
Other intangible assets, net		43	42	46
Lease Acquisition Costs [Member]
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	118	116	123
Amortized intangible assets, Accum. amort.	[1]	(107)	(105)	(111)
Amortized intangible assets, Net value	[1]	11	11	12
Trademarks and Trade Names [Member]
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	20	20	21
Amortized intangible assets, Accum. amort.	[1]	(13)	(13)	(13)
Amortized intangible assets, Net value	[1]	7	7	8
Favorable Leases [Member]
Intangible Assets by Major Class [Line Items]
Amortized intangible assets, Gross value	[1]	7	7	7
Amortized intangible assets, Accum. amort.	[1]	(5)	(5)	(5)
Amortized intangible assets, Net value	[1]	2	2	2
Runners Point Group [Member]
Intangible Assets by Major Class [Line Items]
Indefinite life intangible assets, Net Value	[1]	$ 23	$ 22	$ 24

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