Summary of Significant Accounting Policies (Narrative) (Details) - USD ($) shares in Thousands, $ in Millions		3 Months Ended	12 Months Ended
		Jan. 28, 2017	Jan. 28, 2017	Jan. 30, 2016	Jan. 31, 2015
Significant Accounting Policies [Line Items]
Gift card breakage income			$ 6	$ 5	$ 5
Catalog Costs, amortization period			P90D
Prepaid catalog cost		$ 1	$ 1	$ 2
Contingently issuable shares excluded from diluted earnings per share			200	200	300
Cash equivalents		1,000	$ 1,000	$ 983
Available-for-sale securities		6	6
Capitalized software, net of accumulated amortization		59	59	46
Self-insured liabilities total		$ 12	12	13
Retirement of treasury stock (in shares)		42,000
Restricted Cash and Cash Equivalents, Current		$ 1	1	1
Restricted Cash and Cash Equivalents, Noncurrent	[1]	27	$ 27	$ 26
Additional Paid-In Capital & Common Stock
Significant Accounting Policies [Line Items]
Retirement of treasury stock (in shares)			(42,327)
Retirement of treasury stock		283	$ (283)
Treasury Stock [Member]
Significant Accounting Policies [Line Items]
Retirement of treasury stock (in shares)			42,327
Retirement of treasury stock		1,728	$ 1,728
Retained Earnings
Significant Accounting Policies [Line Items]
Retirement of treasury stock		$ 1,445	(1,445)
Maximum [Member] | Accounting Standards Update 201602 [Member]
Significant Accounting Policies [Line Items]
Addition to Assets and Liabilities from Accounting Standards Update			4,000
Minimum [Member] | Accounting Standards Update 201602 [Member]
Significant Accounting Policies [Line Items]
Addition to Assets and Liabilities from Accounting Standards Update			$ 3,000

[1] Restricted cash is comprised of $23 million of amounts held in escrow in connection with various leasing arrangements in Europe, and $4 million of deposits held in insurance trusts in order to satisfy the requirement to collateralize part of the of the self-insured workers' compensation and liability claims.