The advantage of Thompson Sampling over other algorithms for solving multi-armed bandit problems is its flexibility. Even if the assumptions of the problem change—you have information suggesting one option is better than the others, options depend on one another, options change over time—Thompson’s strategy of pursuing options with a probability that reflects your sense that they are the best currently available still works. So rather than having to derive a new algorithm in each of these cases, we can simply apply Bayes’s Rule and use the results. In real life, those Bayesian calculations can be hard (it took Thompson himself several pages of intricate mathematics to solve the problem with just two options). But trying to choose the best option and allowing an amount of randomness to your choices that is tempered by your degree of certainty is an algorithm that is unlikely to lead you astray.
cited a whopping thirty-two thousand times: The predominant AI textbook, Artificial Intelligence: A Modern Approach, declares that simulated annealing “is now a field in itself, with hundreds of papers published every year” (p. 155).
one of the most promising approaches to optimization: Intriguingly, a 2014 paper appears to demonstrate that jellyfish use simulated annealing in searching for food; see Reynolds, “Signatures of Active and Passive Optimized Lévy Searching in Jellyfish.”
“Not a gambler myself”: Luria, A Slot Machine, a Broken Test Tube, p. 75. Also discussed in Garfield, “Recognizing the Role of Chance.”
coined the term “serendipity”: In Horace Walpole, letter to Horace Mann (dated January 28, 1754).
“A remarkable parallel”: James, “Great Men, Great Thoughts, and the Environment.”
“A blind-variation-and-selective-retention process”: Campbell, “Blind Variation and Selective Retention.”
“Newton, Mozart, Richard Wagner, and others”: Quoted in ibid.
“ways of throwing you out of the frame”: Brian Eno, interviewed by Jools Holland, on Later … with Jools Holland, May 2001.
“vague and constant desire”: The word is saudade, and the quoted definition comes from Bell, In Portugal.
“stupid to shake it up any further”: Tim Adams, “Dicing with Life,” Guardian, August 26, 2000.
10. NETWORKING
“connection has a wide variety of meanings”: Cerf and Kahn, “A Protocol for Packet Network Intercommunication.”
“Only connect”: Forster, Howards End.
“handheld, portable, real cellular phone”: Martin Cooper, “Inventor of Cell Phone: We Knew Someday Everybody Would Have One,” interview with Tas Anjarwalla, CNN, July 9, 2010.
The message was “login”—or would have been: Leonard Kleinrock tells the story in a 2014 video interview conducted by Charles Severence and available at “Len Kleinrock: The First Two Packets on the Internet,” https://www.youtube.com/watch?v=uY7dUJT7OsU.
portentous and Old Testament despite himself: Says UCLA’s Leonard Kleinrock, “We didn’t plan it, but we couldn’t have come up with a better message: short and prophetic.” The tiles on the floor of UCLA’s Boelter Hall, if their colors are interpreted as binary 0s and 1s and parsed as ASCII characters, spell out the phrase “LO AND BEHOLD!” Credit for this tribute goes to architect Erik Hagen. See, e.g., Alison Hewitt, “Discover the Coded Message Hidden in Campus Floor Tiles,” UCLA Newsroom, July 3, 2013, http://newsroom.ucla.edu/stories/a-coded-message-hidden-in-floor-247232.
rooted in the Greek protokollon: See, e.g., the Online Etymology Dictionary, http://www.etymonline.com/index.php?term=protocol.
“They go blast! and they’re quiet”: Leonard Kleinrock, “Computing Conversations: Len Kleinrock on the Theory of Packets,” interview with Charles Severance (2013). See https://www.youtube.com/watch?v=qsgrtrwydjw as well as http://www.computer.org/csdl/mags/co/2013/08/mco2013080006.html.
“utter heresy”: Jacobson, “A New Way to Look at Networking.”
“So little boy went away”: Kleinrock, “Computing Conversations.”
would become known as packet switching: The term “packet switching” comes from Donald W. Davies of the National Physical Laboratory, another key contributor to packet switching research at the time.
“a consensual illusion between the two endpoints”: Stuart Cheshire, personal interview, February 26, 2015.
communications could survive a nuclear attack: Baran, “On Distributed Communications.”
a growing network becomes a virtue: For elaboration on this point, and a broader reflection on the history of networking (including its current problems), see Jacobson, “A New Way to Look at Networking.”
a packet-switching network over “Avian Carriers”: See Waitzman, A Standard for the Transmission of IP Datagrams on Avian Carriers, Waitzman, IP Over Avian Carriers with Quality of Service, and Carpenter and Hinden, Adaptation of RFC 1149 for IPv6 for descriptions of the avian protocol, and see http://www.blug.linux.no/rfc1149 for details of the actual implementation performed in Bergen, Norway, on April 28, 2001.
“No transmission can be 100 percent reliable”: Cerf and Kahn, “A Protocol for Packet Network Intercommunication.”
the “Byzantine generals problem”: Lamport, Shostak, and Pease, “The Byzantine Generals Problem.”
signal that the sequence has been restored: The process being described here is known as “fast retransmit.”
almost 10% of upstream Internet traffic: Jon Brodkin, “Netflix takes up 9.5% of upstream traffic on the North American Internet: ACK packets make Netflix an upload monster during peak viewing hours,” Ars Technica, November 20, 2014. Brodkin in turn cites data from Sandvine’s Global Internet Phenomena Report, https://www.sandvine.com/trends/global-internet-phenomena/.
“Did the receiver crash? Are they just slow?”: Tyler Treat, “You Cannot Have Exactly-Once Delivery,” Brave New Geek: Introspections of a software engineer, March 25, 2015, http://bravenewgeek.com/you-cannot-have-exactly-once-delivery/.
“end-to-end retransmissions to recover”: Vint Cerf, interviewed by Charles Severance, “Computing Conversations: Vint Cerf on the History of Packets,” 2012.
“you just say, ‘Say that again’”: Ibid.
“The world’s most difficult word to translate”: Oliver Conway, “Congo Word ‘Most Untranslatable,’” BBC News, June 22, 2004.
“If at first you don’t succeed”: Thomas H. Palmer, Teacher’s Manual (1840), attested in The Oxford Dictionary of Proverbs, 2009.
trying to link together the university’s seven campuses: Abramson, “The ALOHA System.”
above a mere 18.6% average utilization: Ibid. In fact, this figure is 1⁄2e, exactly half of the n⁄e, or “37%,” figure given in the discussion of optimal stopping in chapter 1.
“only one scheme has any hope of working”: Jacobson, “Congestion Avoidance and Control.”
a pilot program called HOPE: The HOPE program is evaluated in Hawken and Kleiman, Managing Drug Involved Probationers.
“what a crazy way to try to change”: For more information, see, e.g., “A New Probation Program in Hawaii Beats the Statistics,” PBS NewsHour, February 2, 2014.
“this sudden factor-of-thousand drop”: Jacobson, “Congestion Avoidance and Control.”
“then it suddenly fell apart”: Jacobson, “Van Jacobson: The Slow-Start Algorithm,” interview with Charles Severance (2012), https://www.youtube.com/watch?v=QP4A6L7CEqA.
ramp up its transmission rate aggressively: This initial procedure—a tentative single packet followed by a two-for-one acceleration—is known in TCP as Slow Start. This name is a partial misnomer: Slow Start is “slow” in beginning with just a single tentative first packet, but not in its exponential growth thereafter.
“control without hierarchy”: See, e.g., Gordon, “Control without Hierarchy.”
ants’ solution is similar: The findings that link ant foraging to flow control algorithms like Slow Start appear in Prabhakar, Dektar, and Gordon, “The Regulation of Ant Colony Foraging Activity without Spatial Information.”
“tends
to rise to his level of incompetence”: Peter and Hull, The Peter Principle.
“Every public servant should be demoted”: This widely reproduced aphorism, in the original Spanish, reads, “Todos los empleados públicos deberían descender a su grado inmediato inferior, porque han sido ascendidos hasta volverse incompetentes.”
devised by leading law firm Cravath, Swaine & Moore: The Cravath System is officially documented at the firm’s own website: http://www.cravath.com/cravathsystem/. The “up or out” component of the Cravath System is not explicitly discussed there, but is widely referenced elsewhere, e.g., by the American Bar Association: “In the 1920s Cravath, Swaine & Moore became the first law firm on record to openly recruit from law schools with the express understanding that many of the young lawyers it hired would not make partner. Those associates who did not make partner with the rest of their class were expected to leave the firm. However, those deemed best among the associates, who did the necessary work and stayed on track for the requisite number of years, could expect to become stakeholders, earn lockstep increases in compensation, and enjoy lifetime employment in the firm.” (Janet Ellen Raasch, “Making Partner—or Not: Is It In, Up or Over in the Twenty-First Century?,” Law Practice 33, issue 4, June 2007.)
the US Armed Forces adopted: See, e.g., Rostker et al., Defense Officer Personnel Management Act of 1980.
pursued what they call “manning control”: See, e.g., Michael Smith, “Army Corporals Forced Out ‘to Save Pension Cash,’” Telegraph, July 29, 2002.
as if all communication were written text: As Bavelas, Coates, and Johnson, “Listeners as Co-Narrators,” puts it, “Listeners have at best a tenuous foothold in most theories. At the extreme, listeners are considered nonexistent or irrelevant because the theory either does not mention them or treats them as peripheral. This omission may be attributed, in part, to the implicit use of written text as the prototype for all language use.”
“simultaneously engaged in both speaking and listening”: Yngve, “On Getting a Word in Edgewise.”
“Narrators who told close-call stories to distracted listeners”: Bavelas, Coates, and Johnson, “Listeners as Co-Narrators.”
regulating the flow of information from speaker to listener: Tolins and Fox Tree, “Addressee Backchannels Steer Narrative Development.”
“‘bad storytellers’ can at least partly blame their audience”: Jackson Tolins, personal correspondence, January 15, 2015.
“misconceptions about the cause and meaning of queues”: Nichols and Jacobson, “Controlling Queue Delay.”
the HTTP specification still in use today: That is HTTP 1.1, as articulated in the RFC 2616 document from June 1999, available at http://tools.ietf.org/html/rfc2616.
“I happened to be copying, or rsyncing”: Jim Gettys, “Bufferbloat: Dark Buffers in the Internet,” Google Tech Talk, April 26, 2011.
“not ‘Eureka!’ but ‘That’s funny’”: This quotation has appeared in countless publications with an attribution to Isaac Asimov, but its actual authorhip and provenance remain elusive. It seems to have first shown up—complete with the Asimov attribution—as part of the UNIX “fortune” program, which displays quotes or sayings in the style of a fortune cookie. See http://quoteinvestigator.com/2015/03/02/eureka-funny/. Asimov did write an essay about “The Eureka Phenomenon,” but this phrase does not appear there.
when they are routinely zeroed out: See Nichols and Jacobson, “Controlling Queue Delay.”
than her home state of California has people: The US Census Bureau’s 2015 estimate for California’s population was 39,144,818. See http://www.census.gov/popest/data/state/totals/2015/index.html.
“no really good way to leave messages for people”: Ray Tomlinson, interviewed by Jesse Hicks, “Ray Tomlinson, the Inventor of Email: ‘I See Email Being Used, by and Large, Exactly the Way I Envisioned,’” Verge, May 2, 2012, http://www.theverge.com/2012/5/2/2991486/ray-tomlinson-email-inventor-interview-i-see-email-being-used.
simply rejecting all incoming messages: One such approach was taken, for instance, by University of Sheffield cognitive scientist Tom Stafford. During his 2015 sabbatical, his automated email response read: “I am now on sabbatical until 12th June. Email sent to [email protected] has been deleted.”
Explicit Congestion Notification, or ECN: The Request for Comments (RFC) document for ECN is Ramakrishnan, Floyd, and Black, The Addition of Explicit Congestion Notification (ECN) to IP, which is a revision of Ramakrishnan and Floyd, A Proposal to Add Explicit Congestion Notification (ECN) to IP. Though the original proposal dates from the 1990s, ECN remains unimplemented in standard networking hardware today (Stuart Cheshire, personal interview, February 26, 2015).
“This is a long-term swamp”: Jim Gettys, personal interview, July 15, 2014.
“would you say that a Boeing 747 is three times ‘faster’”: This comes from Cheshire’s famous 1996 “rant” “It’s the Latency, Stupid.” See http://stuartcheshire.org/rants/Latency.html. Twenty years later, the sentiment is only truer.
11. GAME THEORY
“I believe humans are noble and honorable”: Steve Jobs, interview with Gary Wolf, Wired, February 1996.
man vs. nature: Appropriately, schoolchildren in the twenty-first century increasingly learn about “person vs. nature,” “person vs. self,” “person vs. person,” and “person vs. society.”
“a clever man would put the poison into his own goblet”: The Princess Bride, screenplay by William Goldman; 20th Century Fox, 1987.
“anticipating the anticipations of others”: Attributed to Keynes in Gregory Bergman, Isms, Adams Media, 2006.
it was the halting problem that inspired Turing: Alan Turing considers the halting problem and proposes the Turing machine in “On Computable Numbers, with an Application to the Entscheidungsproblem” and “On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction.”
“poker players call it ‘leveling’”: Dan Smith, personal interview, September 11, 2014.
“You don’t have deuce–seven”: This took place at the “Full Tilt Poker Durrrr Million Dollar Challenge,” held at Les Ambassadeurs Club in London, November 17–19, 2009, and was televised on Sky Sports.
“only want to play one level above your opponent”: Vanessa Rousso, “Leveling Wars,” https://www.youtube.com/watch?v=Yt5ALnFrwR4.
“knowing or trying to know what Nash is”: Dan Smith, personal interview, September 11, 2014.
a so-called equilibrium: The concept of a game-theoretic equilibrium—and, for that matter, game theory itself—comes from Princeton’s John von Neumann and Oskar Morgenstern in Theory of Games and Economic Behavior.
In rock-paper-scissors, for example: For a colorful look into rock-paper-scissors (“RPS”) tournament play, including a glossary of the game’s various three-move “gambits”—like the Avalanche (RRR), the Bureaucrat (PPP), and Fistful o’ Dollars (RPP)—we recommend http://worldrps.com. For a look into computer RPS play, check out the Rock Paper Scissors Programming Competition: http://www.rpscontest.com.
choose one of the eponymous hand gestures completely at random: A strategy, like this one, that incorporates randomness is called a “mixed” strategy. The alternative is a “pure” strategy, which always involves taking the exact same option; this clearly would not work for long in rock-paper-scissors. Mixed strategies appears as part of the equilibrium in many games, especially in “zero-sum” games, where the interests of the players are pitted directly against one another.
every two-player game has at least one equilibrium: Nash, “Equilibrium Points in N-Person Games”; Nash, “Non-Cooperative Games.”
the fact that a Nash equilibrium always exists: To be more precise, ibid. proved that every game with a finite number of players and a finite number of strategies has at least one mixed-strategy equilibrium.
“has had a fundamental and pervasive impact”: Myerson, “Nash Equilibrium and the History of Economic Theory.”
“a c
omputer scientist’s foremost concern”: Papadimitriou, “Foreword.”
“Give us something we can use”: Tim Roughgarden, “Algorithmic Game Theory, Lecture 1 (Introduction),” Autumn 2013, https://www.youtube.com/watch?v=TM_QFmQU_VA.
all been proved to be intractable problems: Gilboa and Zemel, “Nash and Correlated Equilibria.”
simply finding Nash equilibria is intractable: Specifically, finding Nash equilibria was shown to belong to a class of problems called PPAD, which (like NP) is widely believed to be intractable. The link between Nash equilibria and PPAD was established in Daskalakis, Goldberg, and Papadimitriou, “The Complexity of Computing a Nash Equilibrium” and Goldberg and Papadimitriou, “Reducibility Between Equilibrium Problems,” which was then extended to two-player games by Chen and Deng, “Settling the Complexity of Two-Player Nash Equilibrium,” and then further generalized in Daskalakis, Goldberg, and Papadimitriou, “The Complexity of Computing a Nash Equilibrium.” PPAD stands for “Polynomial Parity Arguments on Directed graphs”; Papadimitriou, who named this class of problems in “On Complexity as Bounded Rationality,” insists any resemblance to his name is a coincidence. (Christos Papadimitriou, personal interview, September 4, 2014.)
PPAD contains other interesting problems, such as the ham sandwich problem: given n sets of 2n points in n dimensions, find a plane that divides each set of points exactly in half. (With n = 3, this involves figuring out the path a knife would have to travel to cut three sets of points in half; if those sets of points correspond to two pieces of bread and a piece of ham, the result is a perfectly bisected sandwich.) Finding Nash equilibria is actually PPAD-complete, meaning that if there were an efficient algorithm for solving it then all other problems in the class could also be solved efficiently (including making the world’s neatest sandwiches). But being PPAD-complete is not quite so bad as being NP-complete. P, the class of efficiently solvable problems, could be equal to PPAD without being equal to NP. As of this writing the jury is still out: it’s theoretically possible that somebody could devise an efficient algorithm for finding Nash equilibria, but most experts aren’t holding their breath.
Algorithms to Live By Page 41