Browsing by Subject "Game theory"

Game theory involves the study of how self-interested agents interact in various settings. Perhaps the best-known game theoretic solution concept is that of Nash equilibrium. However, Nash equilibrium makes a number of assumptions, such as rationality of all of the players and the ability of the players to choose the same equilibrium when more than one exists. Because of these assumptions, it is unclear if simply solving for Nash equilibrium is always the correct thing to do. In some settings, one player can instead credibly commit to a strategy, and communicate this to the other player, before the other player can make a decision. This has become known as a Stackelberg game. Computing optimal strategies to commit to in normal-form or Bayesian Stackelberg games is a topic that has recently been gaining attention, in part due to the application of such algorithms in various security and law enforcement scenarios. My work on Stackelberg games falls into three main areas.

First, I focus on general games, where we give efficient algorithms and hardness results for Bayesian, extensive-form and stochastic games. In each of these settings we study the relationship between different modeling assumptions and the tractability of finding an optimal strategy to commit to. For Bayesian games our results are mainly negative; we show that not only are the problems here NP-hard, but in many cases they are also inapproximable. Our results for extensive-form games are more mixed; we are able to give polynomial time algorithms for four cases. However, we also show that if we relax the assumptions made in these four cases, then the problem usually becomes NP-hard. Finally, our results for stochastic games are again somewhat negative, as we show that the problem is NP-hard is most reasonable cases. However, here we are also able to give an approximation algorithm to compute optimal commitment strategies in a setting where correlation is allowed.

I next focus on Stackelberg security games. Stackelberg security games usually involve the scheduling of scarce defense resources to cover some subset of potential targets. We first study methods for going from marginal solutions (which ignore overlapping coverage between different schedules) to valid mixed commitment strategies in graphical settings. Here we are able to characterize two new classes of games where mixed strategies corresponding to the marginal probabilities are guaranteed to exist, and give algorithms for finding them. Next, we offer a simple model of interdependencies between nodes in a network based on probabilistic failure cascades, extending the well-known independent cascade model of the spread of infectious diseases or ideas. We give an algorithm for this problem and experimentally show that this algorithm scales to realistic security settings and outperforms the state of-the-art alternatives. Finally, we create an approach for optimal interdiction of attack plans. We show how to model an attack plan interdiction problem as a large-scale integer linear program similar to an integer programming approach for solving partial satisfaction planning problems. We also give several oracle-based approaches for solving this and then evaluate them experimentally.

Third, I analyze how much benefit a player can derive from commitment in various types of games, in a quantitative sense that is similar to known concepts such as the value of mediation and the price of anarchy. To do this we introduce and study the value of pure commitment (the benefit of committing to a pure strategy), the value of mixed commitment (the benefit of committing to a mixed strategy), and the mixed vs. pure commitment ratio (how much can be gained by committing to a mixed strategy rather than a pure one).

This dissertation explores decision problems faced by organizations willing to address or support the incorporation of sustainability aspects on their "business as usual" activities. We study to specific problems. First, we analyze the decision problem of a forest manager who, in addition to selling timber, has the option of selling carbon offsets for the carbon sequestered by the forest. We study both the single-rotation and the multiple-rotations harvesting problems, and develop stochastic dynamic programming models to find the optimal harvesting and offset-selling policy, the expected optimal harvesting time, and the expected optimal reward under different offset-trading schemes. Then, we study the case in which an organization (sustainability buyer) outsources sustainability efforts to another organization (sustainability seller). While buyers cannot directly exert sustainability efforts, they can provide economic or technical support to their sellers in order to incentivize these efforts. We investigate how the effort and support decisions change according to characteristics of stakeholders, buyers, and sellers. Considering that buyers can compete on the sustainability effort exerted by their sellers, we extend our analysis to the case of competing buyers, and we determine conditions under which sharing sellers is preferred by the buyers to having separate sellers for each buyer.

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

A majority of formal theoretic research in political science treats political parties as unitary actors, and endows them with decision-making powers not unlike those of strategic individuals. This is true both of most research in the spatial-theoretic tradition, as well as most game theoretic research in the field of comparative political-economy. In contrast, my dissertation examines strategic equilibria which arise when competition takes place simultaneously within parties over organizational control and between parties over political office. I first distinguish between three intra-organizational elements: a party's parliamentary group, its activist cadre, and its executive leaders. Chapters 2-4 develop a set of foundational game theoretic models which identify the equilibrium balance of power among these 3 organizational elements as a function of a country's electoral institutions and voters' relative responsiveness to marginal policy changes. In turn, this more complete understanding of intra-party competition sheds light on a number of important questions in comparative politics and comparative political-economy. For example, it helps to identify conditions under which Downsian vote-maximization is in fact a viable assumption in spatial theoretic models; conditions under which Duverger's argument that proportional representation (PR) should tend to generate multi-party competition may not apply; and, in contrast to Lijphart's famous argument, conditions under which PR may instigate rather than mediate social conflict. Ten months of intensive field research conducted in Turkey provide both the quantitative and the qualitative data which constitute the dissertation's most basic empirical material. This data includes primary and secondary source material on the history of intra-organizational competition in Turkey; observational and informant-based information on contemporary Turkish politics and the events of 2006-2008; and a data set of over 4,000 observations on party-switching in the Turkish Parliament (1987-2007).

The ability to digitize information goods such as music and movies and the growing accessibility of the Internet has led to online piracy and the emergence of a new class of retailers that specialize in digital downloads. Both online piracy and digital retailers have changed the dynamics of the information goods distribution channel. In my dissertation I focus on issues related to this change.

In the first chapter, "Digital music set free: the flip side of DRM," I study the effect of Digital Rights Management (DRM) mechanisms on the competition between traditional and digital retailers and on online piracy. DRM refers to technologies designed to control how end users may access, copy, or convert digital media. In the context of music downloads, DRM makes piracy of digital music more difficult, and until recently, most legal outlets for downloadable music only sold songs with DRM protection. Recently download retailers have convinced record companies to allow them to sell DRM-free music. The introduction of DRM-free music raises several important questions: Will music piracy increase as the opponents of DRM-free music predict? Will the music industry profits go up or down? How will CD retailers be affected? Will all labels start selling the unprotected (DRM-free) content?

I address these and related questions by developing a model of a music distribution channel that allows a record label to sell through both traditional CD retailers and iTunes-like download services at different wholesale prices. Among the interesting results, the analysis indicates that the level of piracy may decline when DRM protection is removed and that the traditional retailers much prefer to compete with distributors of pirated digital music rather than with legal music download services.

The competition between online and traditional retailers has led to interesting pricing policies on which I focus in the second chapter, "Digital movies at one simple price: the effect on competition." Online retailers tend to prefer uniform pricing (e.g. iTunes Store) where all "products" carry a single price, while traditional retailers do not have a policy of uniform prices. It is important to understand why one retailer should choose a single, uniform price and what impact it has on the competing retailer who chooses multiple prices. I focus specifically on the impact that single price policy adopted by digital retailer has on the traditional retailer. I also analyze the choice of uniform vs. differentiated pricing by modeling the competition between online and traditional retailers for vertically differentiated information goods. Importantly, I demonstrate how the asymmetric equilibrium we observe in the market today can change systematically with the nature of competition between the retailers.

This dissertation studies dynamic tournaments and their economic and managerial implications from two different perspectives. The first half focuses on the optimal timing of information release when a tournament uses a feedback scheme, while the other half investigates the impact of the use of mercy rule in a dynamic tournament on the economic output and other system wide characteristics.

In Chapter 2, we study dynamic tournaments in which time is modeled explicitly, as opposed to with the abstract notion of ``periods.'' By doing so, we characterize the effects of the ex-ante-designated timing of an interim progress report. Whether or not a policy of reporting increases total expected effort does not depend on the release time of the report, however the magnitude of the effect does. We demonstrate that total expected effort is single-peaked or single-troughed in the report's release time depending on parameters, with the peak/tough located at a time strictly more than halfway through the tournament. However, a policy of releasing information always harms the expected utility of the tournament's participants. Implications for tournament design are discussed.

Chaper 3 explores dynamic tournaments in a continuous space and continuous

time framework, in which contestants can observe their opponents' progresses

in real time and have the opportunity to end the contest early when one's

lead over the other is larger than some pre-determined threshold (a.k.a a

mercy rule). We first show that the game has a unique equilibrium, then characterize

the equilibrium numerically, and investigate the impacts of mercy rules on

tournament design. By doing so, we find that there exists an optimal mercy

rule that induces the best economic output, even though players always prefer a

tournament without a mercy rule. Depending on the cost and noises

parameters, a non-monotonic mercy rule may perform better. We also consider

the scenario in which players prefer to end the game early because of

outside options and have the choice to drop out. Given an exogenous mercy

rule, this drop-out option endogenizes another boundary. And surprisingly,

the endogenous mercy rule is not always dominated by the exogenous rule in

terms of inducing efforts.

This dissertation comprises two chapters studying how information transmitted in the economy and the financial markets becomes compressed in communications and its consequences. In chapter one, the compression is due to limited communication bandwidth, and in chapter two, it is due to limited attention on the receiver’s end.

Chapter one discusses how information intermediaries selectively present evidence to serve financial decision-makers. Faced with a space limit for their communication reports, the information intermediaries present information selectively. I solve the model for the optimal messages in the intermediaries' communication with the decision-makers and investigate the relationship between the apparent messages and the inferred economic fundamentals. The two main findings are: (i) the model matches many stylized facts about content biases such as prior or extreme biases; (ii) I derive an analytical relationship between the messages and the inferred fundamentals in the asymptotics. This relationship can be conveniently used to interpret observed content biases and quantitatively analyze the effects of the context on the interpretation of contents. The theory also shows that content biases may improve rather than decrease welfare. The model relates to empirical content analysis using frequency-based proxies and can be used to analyze contextual effects on contents.

In chapter two, I develop and analyze a theoretical model that shows how investors allocate their limited attention resources to monitor a wide selection of target firms. An investor with limited attention demands information about the types of her portfolio firms before investing. The firms strategically supply good news and withhold bad news. The investor may press companies to reveal more information by allocating more costly attention to them. Because the benefit to attention is convex, the investor will optimally focus on a subset of firms and acquire complete information while giving up learning anything about the other firms. Firms in the scrutinized subset have low investigation costs and a high Expected Value of Perfect Information (EVPI), and they always receive an efficient amount of capital. The other firms are provided with an inefficient level of capital and suffer from extreme asymmetry in information transparency. The result rationalizes convertible debt as a socially optimal financing instrument for private firms. It can be applied to a venture capital context to analyze entrepreneurial investment relationships.

This dissertation studies operations management problems in service operations and supply chains, analyzing the impact of strategic customers and disruptive technologies. We investigate three problems, and insights from the study of each one illuminate the effect of information and/or strategic customer behavior on decision makers in operations management systems.

The first problem involves the strategic routing behavior of customers in a service network with multiple stations, when customers can choose the order of stations that they visit. We propose a two-station game with all customers present at the start of service and deterministic service times, and we find that strategic customers "herd," i.e., in equilibrium all customers choose the same route. For unobservable systems, we prove that the game is supermodular, and we then identify a broad class of learning rules---which includes both fictitious play and Cournot best-response---that converges to herding in finite time. By combining different theoretical and numerical analyses, we find that the herding behavior is prevalent in many other congested open-routing service networks, including those with arrivals over time, those with stochastic service times, and those with more than two stations. We also find that the system under herding performs very close to the first-best outcome in terms of cumulative system time.

The second problem relates to a disruptive, on-demand delivery platform who provides delivery from an independent sit-down restaurant. Food delivery platforms maintain a symbiotic relationship with the existing providers in their industry; rather than "stealing" demand from an established player, these platforms work with restaurants to connect customers with the restaurant's product by providing an additional purchase channel. We model the restaurant as a queueing system with customer waiting costs. First, we solve the revenue maximization problem faced by a monopolist who controls both the dine-in and delivery prices and receives all revenues from the system. These results are related to the priority queueing and pricing literature and are of independent interest. We also demonstrate that a coordination problem exists between the restaurant and platform. We then investigate means of coordinating this supply chain via different contracts between the restaurant and the platform. We find that a two-way revenue-sharing contract coordinates the supply chain.

Finally, our third problem is spawned from an industry collaboration aimed at improving the inventory planning decisions of a company that sells high-tech goods with short life cycles. We develop a novel heuristic based on a power approximation in the extant literature. The power approximation computes near-optimal (s,S) policies for infinite-horizon inventory problems. We propose a new form of this approximation, devised using real demand data from our industry partner, and a heuristic based on the approximation that updates the inventory policy as new demand forecasts are generated. We evaluate the performance of our heuristic---also on real demand data, though for a different time period and for different items than were used to fit our model---and find that it performs quite well.

This dissertation employs game theoretic techniques to examine various topics in international relations and law. Chapter 2 uses a crisis bargaining model that accounts for prior bargaining agreements to study the conditions under which states choose to engage in multiple wars over different issues. I find that a proposing state is willing to risk war with multiple states when they are overly optimistic about the state they are currently bargaining with being weak.

Chapter 3 uses a game theory model of complete information to study the conditions under which a third-party state will intervene in a civil conflict when it must account for a potential retaliation by another external state. I find that when choosing to intervene or not, the potential intervening state must weigh the costs of military action by the retaliating state and the political ramifications of issuing an empty threat against each other.

Finally, Chapter 4 uses a game theory model of asymmetric information to analyze how a criminal defendant's ability to crowdfund legal fees can impact a prosecutor's plea bargaining decision. I find that a prosecutor will offer a relatively lenient plea deal to defendants whom they perceive to have a high ability and can make the trial costs high, or who they believe are low ability defendants while facing high political costs. On the other hand, they will offer relatively harsh plea deals to defendants whom they perceive to have a high ability and the trial cost is low, or who they believe have a low ability while facing low political costs.

This dissertation uses game-theoretic modeling, statistical testing, and case studies to analyze how authoritarian governments manage the news media to maintain regime stability, control local officials, and make reform. In the first essay, ``Regime Competence and Media Freedom in Authoritarian States'', I explain why some authoritarian regimes allow more media freedom than others, as they tradeoff increased rents when the media is suppressed with the reduced risk of being misjudged by citizens when the media is free. In the second essay, ``Local Media Freedom, Protest Diffusion, and Authoritarian Resilience'', I argue that media reports about citizen protests, which may lead to protest diffusion, do not necessarily destabilize authoritarian rule. If protests are targeted at local governments, the central government of an authoritarian regime can use media-induced protest cascades to force local officials to improve governance. In the last essay, ``Central Rhetoric and Local Reform in China'', I address the puzzle of why the Chinese government would furnish the state media with conservative and dogmatic rhetoric on the one hand and allow reform on the other, by showing that this strategy is used to control local governments' pace of reform.

This dissertation studies the use of information design to reduce the spread of an infection. In particular, I investigate whether central planners (senders) with more information can leverage the information advantage to improve social welfare. In the first chapter, I analyze a single sender's best information revelation policy when individuals (receivers) have heterogeneous social activity levels and decide their binary protection levels, which further determine a transmission network over which the infection spreads. I establish that it is optimal to obfuscate information only for intermediate transmission rates and for small initial infection probabilities. In the second chapter, I further explore the use of information when there are multiple senders, each caring their own population. I characterize the population's equilibrium actions given any information and the equilibrium information disclosure policies between two senders. I establish that the two senders will disclose no information when they are either heavily economically concerned with high economic costs and a low prior belief about the disease, or health concerned with low economic costs. The senders will disclose partial information when one sender is heavily economically concerned with high economic costs and a high prior belief about the disease, while the other sender is either heavily economically concerned with high economic costs or health concerned with low economic costs. The senders will disclose full information when at least one sender is either concerned but not extremely concerned about the economy or health concerned with high economic costs.

The last decade has witnessed the rapid growth of many innovative and disruptive business models. This dissertation identifies a few of the unique inefficiencies and challenges that these new business models bring for small entrepreneurs and recommends ways to solve them.

The second and third chapters of this dissertation focus on rewards-based crowdfunding platforms such as Kickstarter and Indiegogo, where entrepreneurs designing new and innovative products solicit monetary pledges from a population of potential contributors. If total pledges exceed a pre-specified funding target, the entrepreneur distributes non-monetary rewards—typically, units of the new product—to these contributors. Otherwise, the contributors are refunded their pledges.

The second chapter explores how an entrepreneur might overcome one of the most significant challenges in crowdfunding: credibly signaling information about the quality of the new product to a pool of small, uninformed contributors. We find that the entrepreneur should signal high quality by setting a high target that is distorted above the full information optimal level. While a separating equilibrium always exists, a pooling equilibrium can only occur under very specific circumstances. We show that the high target affects the quality choice of entrepreneurs and may deter unique, high quality projects. In addition, we discuss how the entrepreneur should modify the signaling strategy when a high target potentially deters backers from pledging due to the cost of participating in a failed campaign.

The third chapter explores how to design such crowdfunding campaigns when contributors choose not just whether to contribute, but also when to contribute. We show that strategic contribution behavior—when contributors intentionally delay their pledges until campaign success is likely—can arise from the combination of non-refundable (potentially very small) hassle costs and the risk of campaign failure, and can explain pledging patterns commonly observed in crowdfunding. Furthermore, such delays hurt the entrepreneur if contributors are distracted, i.e., if they may fail to return to the campaign after an intentional delay. To mitigate this, an entrepreneur can use a simple menu of two rewards with a fixed number of units sold at a low price, and an unlimited number sold at a higher price; this segments contributors over time based on the information they observe upon arrival. Despite its simplicity, such a menu performs well compared to a theoretically optimal menu consisting of an infinite number of different rewards and price levels under many conditions.

The fourth chapter focuses on another business model: subscription box services that deliver shipments of products to consumers at regular intervals for a fixed, per-box fee. Two challenges for providers of such services are acquiring new subscribers and retaining existing ones. We show that providers can respond to these challenges by managing the content of their subscription boxes over time when selling to customers that are heterogeneous along two dimensions: their utility for the contents of each box, and their utility for the service of content curation and delivery. The provider faces a budget for the total value (i.e., the quality) of box contents over a finite time horizon, and must allocate that budget over time to maximize total demand. Allocating more budget to a particular period increases consumer utility for the box—and hence the subscription rate—in that period, but at the expense of reducing the remaining budget for other periods. We show that it is generally not optimal for the service provider to allocate her budget equally and maintain consistent quality over time. If consumer heterogeneity is low, the optimal content strategy is to increase quality over time, which prioritizes retention over initial acquisition (i.e., quality starts low, acquiring few consumers, but increases to induce consumers to continue subscribing). On the other hand, if heterogeneity is high, the optimal strategy is to decrease quality over time, prioritizing acquisition over retention (i.e., quality starts high, acquiring many consumers, but decreases over time, retaining only consumers who highly value the service).

Algorithms for finding game-theoretic solutions are now used in several real-world security applications. Many of these applications are based on different but related game-theoretical models collectively known as security games. Much of the research in this area has focused on the two-player setting in which the first player (leader, defender) commits to a strategy, after which the second player (follower, attacker) observes that strategy and responds to it. This is commonly known as the Stackelberg, or leader-follower, model. If none of the players can observe the actions of the others then such a setting is called a simultaneous-move game. A common solution concept in simultaneous-move games is the Nash equilibrium (NE). In the present dissertation, we contribute to this line of research in two ways.

First, we consider new ways of modeling commitment. We propose the new model in which the leader can commit to a correlated strategy. We show that this model is equivalent to the Stackelberg model in two-player games and is different from the existing models in games with three or more players. We propose an algorithm for computing a solution to this model in polynomial time. We also consider a leader-follower setting in which the players are uncertain about whether the follower can observe. We describe an iterative algorithm for solving such games.

Second, we analyze the computational complexity of computing Stackelberg and NE strategies in security games. We describe algorithms to solve some variants of the security game model in polynomial time and prove NP-hardness of solving other variants of the model. We also extend the family of security games by allowing the attacker have multiple resources. We provide an algorithm for computing an NE of such games in polynomial time, and we show that computing a Stackelberg strategy is NP-hard.

Search advertising refers to the practice where advertisers place their text-based advertisement on the search engine's result page along with the organic search results. With its growing importance, search advertising has seen a recent surge in academic interest. However, the literature has been ignoring some practical yet important problems of advertisers, including the keyword selection problem. In my dissertation, I focus on the keyword selection problem, more specifically, the choice of branded keywords in search advertising.

My dissertation begins with an observation on different patterns of branded keyword purchase behavior by the brand owner and its competitor. Under some branded keywords, we observe in the sponsored link, only the brand owner or only the competitor. However, under some other branded keywords, we observe both firms, or neither of them. Upon this phenomenon, I aim to understand what drives this puzzling pattern in a competitive environment. To this purpose, I develop a duopoly model where two firms compete in the product market with both horizontally and vertically differentiated products. Their products are evaluated by consumers whose perception is affected by what they see in search advertising. With this setup, Then I derive a subgame perfect equilibrium of the two stage game.

In a pricing equilibrium, I find that any benefit a firm gets from search advertising either due to exposure benefit or due to contrast or assimilation, helps this firm charge higher price while forcing the other firm charge lower price. This result affects the incentive for each firm to buy the branded keyword in the advertising stage. Specifically, firms have an incentive to buy the keyword only when the cost of advertising is justified by the exposure benefit but even in that case, each firm buys only when the detrimental context effect is not present. If the quality difference between the brand owner and the competitor is large and thus there exists a contrast between the two firms, the competitor with low quality product refrains from buying the keyword, because the contrast effect hurts the competitor. On the other hand, if the quality difference is small and thus two brands are assimilated, the brand owner with high quality product refuses to buy the keyword, because it is hurt by the assimilation effect. If the quality difference is in the intermediate range so that neither context effect is harmful to neither firm, both firms buy the keyword at the same time. On probing further the underlying incentives, I find that in some cases, the brand owner may buy its own keyword only to defend itself from the competitor's threat. In contrast, I also identify the case where the brand owner chooses to buy its own keyword and precludes the competitor from buying it. My result also suggests that both firms may be worse off by engaging in advertising, as in the prisoner's dilemma case.

On an extension, I provide an analysis on the impact of the insufficient advertising budget. If the budget is limited, both firms may have an incentive to hurt the other firm taking the higher slot, by increasing the bid amount and thus quickly exhausting the competitor's budget. The budget constraint also deprives the advertisers of the incentive to buy the keyword and thus, the budget-constrained advertisers may refuse to match the competitor's purchase of the keyword. Finally, the experimental investigation shows the existence of the exposure effect and the context effects. It also supports the model prediction based on estimated model parameters together with the empirical observation.

This dissertation describes sequential decision making problems in non-stationary environments. Online learning algorithms deal with non-stationary environments, but generally there is no notion of a dynamic state to model future impacts of past actions. State-based models are common in stochastic control settings, but well-known frameworks such as Markov decision processes (MDPs) assume a known stationary environment. In recent years, there has been a growing interest in fusing the above two important learning frameworks and considering an MDP setting in which the cost function is allowed to change arbitrarily over time. A number of online MDP algorithms have been designed to work under various assumptions about the dynamics of state transitions so far and provide performance guarantees, i.e. bounds on the regret defined as the performance gap between the total cost incurred by the learner and the total cost of the best available stationary policy that could have been chosen in hindsight.

However, most of the work in this area has been algorithmic: given a problem, one

would develop an algorithm almost from scratch and prove the performance guarantees on a case-by-case basis. Moreover, the presence of the state and the assumption of an arbitrarily varying environment complicate both the theoretical analysis and the development of computationally efficient methods. Another potential issue is that, by removing distributional assumptions about the mechanism generating the cost sequences, the existing methods have to consider the worst-case scenario, which may render their solutions too conservative in situations where the environment exhibits some degree of predictability.

This dissertation contributes several novel techniques to address the above challenges of the online MDP framework and opens up new research directions for online MDPs.

Our proposed general framework for deriving algorithms in the online MDP setting leads to a unifying view of existing methods and provides a general procedure for constructing new ones. Several new algorithms are developed and analyzed using this framework. We develop convex-analytical algorithms that take advantage of possible regularity of observed sequences, yet maintain the worst case performance guarantees. To further study the convex-analytic methods we applied above, we take a step back to consider the traditional MDP problem and extend the LP approach to MDPs by adding a relative entropy regularization term. A computationally efficient algorithm for this class of MDPs is constructed under mild assumptions on the state transition models. Two-player zero-sum stochastic games are also investigated in this dissertation as an important extension of the online MDP setting. In short, this dissertation provides in-depth analysis of the online MDP problem and answers several important questions in this field.