This dissertation makes contributions to areas of research on planning with POMDPs: complexity theoretic results and heuristic techniques. The most important contributions are probably the complexity of approximating the optimal history-dependent finite-horizon policy for a POMDP, and the idea of heuristic search over the space of FFTs.

We propose a new approach to optimize operations of hydro storage systems with multiple connected reservoirs whose operators participate in wholesale electricity markets. Our formulation integrates short-term intraday with long-term interday decisions. The intraday problem considers bidding decisions as well as storage operation during the day and is formulated as a stochastic program. The interday problem is modeled as a Markov decision process of managing storage operation over time, for which we propose integrating stochastic dual dynamic programming with approximate dynamic programming. We show that the approximate solution converges towards an upper bound of the optimal solution. To demonstrate the efficiency of the solution approach, we fit an econometric model to actual price and in inflow data and apply the approach to a case study of an existing hydro storage system. Our results indicate that the approach is tractable for a real-world application and that the gap between theoretical upper and a simulated lower bound decreases sufficiently fast. (authors' abstract)

This paper presents a novel algorithm for learning in a class of stochastic Markov decision processes (MDPs) with continuous state and action spaces that trades speed for accuracy. A transform of the stochastic MDP into a deterministic one is presented which captures the essence of the original dynamics, in a sense made precise. In this transformed MDP, the calculation of values is greatly simplified. The online algorithm estimates the model of the transformed MDP and simultaneously does policy search against it. Bounds on the error of this approximation are proven, and experimental results in a bicycle riding domain are presented. The algorithm learns near optimal policies in orders of magnitude fewer interactions with the stochastic MDP, using less domain knowledge. All code used in the experiments is available on the project's web site.

We analyze the problem of distributing units of a product, by a capacitated vehicle, from one storage location (depot) to multiple retailers. The demand processes at the retailers are stochastic and time-dependent. Based on current inventory information, the decision maker decides how many units of the product to deposit at the current retailer, or pick up at the depot, and which location to visit next. We refer to this problem as the stochastic vendor managed inventory (SVMI) problem. In the Markov decision process model of the SVMI problem, we show how a retailer continues to be the vehicle's optimal destination as inventory levels of the retailers vary. Furthermore, an optimal inventory action is shown to have monotone relations with the inventory levels. The multi-period SVMI problem and the infinite horizon (periodic) SVMI problem are analyzed. Additionally, we develop three suboptimal solution procedures, complete a numerical study, and present a case study, which involves a distribution problem at the Coca-Cola Enterprises, Inc. We consider four variations of the SVMI problem, which differ in the available state information and/or the vehicle routing procedure. Analytically, we compare the optimal expected total rewards for the SVMI problem and its variations. Our computational experience suggests a complementary relationship between the quality of state information and the size of the set of retailers that the vehicle can visit.

The majority of the research conducted on consumer choice phenomena focuses on how choices are made and the processes that lead up to those choices. While these are essential aspects within the breadth of choice knowledge that exists today, little research has been conducted on the options that are rejected during this process. Thus, the overarching goal of this dissertation is gain an understanding of consumer choice processes and outcomes through the lens of a nearly chosen alternative. Specifically, this dissertation investigates how the decision process can cause a close second option to be rejected when the chosen option is found to be unavailable.As a means of achieving these goals, I first demonstrate the phenomenon that consumers do not always select a close second option when the first choice option is unavailable, contrary to the prediction of economic rationality. Next, I propose that the decision process itself, specifically the use of a tie-breaking attribute to differentiate between close options, triggers a choice outcome that does not include the original second choice option, but rather an alternative that possesses this tie-breaking attribute. Finally, I examine the implications that the preference reversal phenomenon described above has for retailers and manufacturers.My original interest in this phenomenon stems from anecdotal evidence provided by a variety of informants. Although this evidence helped me to recognize the prevalence of rejected second choice options, experimental design is used to investigate this phenomenon and the boundary conditions that confine this effect. Consequently, my dissertation consists of 6 experiments. Experiment 1 and a pilot study establish the effect and investigate the theoretical process that account for my findings. Experiments 2 through 4 rule out alternative explanations and add support towards the existence and prevalence of the effect. Finally, Experiments 5 and 6 explore the impact of these results for improving the performance of marketing managers. It is my belief that incorporating the dynamic effects of the second-most preferred option may ultimately lead to more accurate and sophisticated prediction of buyer choices, more effective retailing and personal selling strategies, and more profitable management of product line portfolios.

This thesis provides a discussion on some analytical and empirical models of online auctions. The objective is to provide an alternative framework for analyzing online auctions, and to characterize the distribution of intermediate prices. Chapter 1 provides a mathematical formulation of the eBay auction format and background to the data used in the empirical analysis. Chapter 2 analyzes policies for optimally disposing inventory using online auctions. It is assumed a seller has a fixed number of items to sell using a sequence of, possibly overlapping, single-item auctions. The decision the seller must make is when to start each auction. The decision involves a trade-off between a holding cost for each period an item remains unsold, and a cannibalization effect among competing auctions. Consequently the seller must trade-off the expected marginal gain for the ongoing auctions with the expected marginal cost of the unreleased items by further deferring their release. The problem is formulated as a discrete time Markov Decision Problem. Conditions are derived to ensure that the optimal release policy is a control limit policy in the current price of the ongoing auctions. Chapter 2 focuses on the two item case which has sufficient complexity to raise challenging questions. An underlying assumption in Chapter 2 is that the auction dynamics can be captured by a set of transition probabilities. Chapter 3 shows with two fixed bidding strategies how the transition probabilities can be derived for a given auction format and bidder arrival process. The two specific bidding strategies analyzed are when bidders bid: 1) a minimal increment, and 2) their true valuation. Chapters 4 and 5 provides empirical analyzes of 4,000 eBay auctions conducted by Dell. Chapter 4 provides a statistical model where over discrete time periods, prices of online auctions follow a zero-inflated gamma distribution. Chapter 5 provides an analysis of the 44,000 bids placed in the auctions, based on bids following a gamma distribution. Both models presented in Chapters 4 and 5 are based on conditional probabilities given the price and elapsed time of an auction, and certain parameters of the competing auctions. Chapter 6 concludes the thesis with a discussion of the main results and possible extensions.

Start-up firms play an important role in the economy. Statistics show that a large percent of start-up firms fail after few years of establishment. Raising capital, which is crucial to success, is one of the difficulties start-up firms face. This Ph. D thesis aims to draw suggestions for start-up firm survival from mathematical models and numerical investigations. Instead of the commonly held profi t maximizing objective, this thesis assumes that a start-up firm aims to maximize its survival probability during the planning horizon. A firm fails if it runs out of capital at a solvency check. Inventory management in manufacturing start-up firms is discussed further with mathematical theories and numerical illustrations, to gain insight of the policies for start-up firms. These models consider specific inventory problems with total lost sales, partial backorders and joint inventory-advertising decisions. The models consider general cost functions and stochastic demand, with both lead time zero and one cases. The research in this thesis provides quantitative analysis on start-up firm survival, which is new to the literature. From the results, a threshold exists on the initial capital requirement to start-up firms, above which the increase of capital has little effect on survival probability. Start-up firms are often risk-averse and cautious about spending. Entering the right niche market increases their chance of survival, where the demand is more predictable, and start-ups can obtain higher backorder rates and product price. Sensitivity tests show that selling price, purchasing price and overhead cost have the most impact on survival probability. Lead time has a negative effect on start-up firms, which can be offset by increasing the order frequent. Advertising, as an investment in goodwill, can increase start-up firms' survival. The advertising strategies vary according to both goodwill and inventory levels, and the policy is more flexible in start-up firms. Externally, a slightly less frequency solvency check gives start-up firms more room for fund raising and/or operation adjustment, and can increase the survival probability. The problems are modelled using Markov decision processes, and numerical illustrations are implemented in Java.

This thesis provides a discussion on some analytical and empirical models of online auctions. The objective is to provide an alternative framework for analyzing online auctions, and to characterize the distribution of intermediate prices. Chapter 1 provides a mathematical formulation of the eBay auction format and background to the data used in the empirical analysis. Chapter 2 analyzes policies for optimally disposing inventory using online auctions. It is assumed a seller has a fixed number of items to sell using a sequence of, possibly overlapping, single-item auctions. The decision the seller must make is when to start each auction. The decision involves a trade-off between a holding cost for each period an item remains unsold, and a cannibalization effect among competing auctions. Consequently the seller must trade-off the expected marginal gain for the ongoing auctions with the expected marginal cost of the unreleased items by further deferring their release. The problem is formulated as a discrete time Markov Decision Problem. Conditions are derived to ensure that the optimal release policy is a control limit policy in the current price of the ongoing auctions. Chapter 2 focuses on the two item case which has sufficient complexity to raise challenging questions. An underlying assumption in Chapter 2 is that the auction dynamics can be captured by a set of transition probabilities. Chapter 3 shows with two fixed bidding strategies how the transition probabilities can be derived for a given auction format and bidder arrival process. The two specific bidding strategies analyzed are when bidders bid: 1) a minimal increment, and 2) their true valuation. Chapters 4 and 5 provides empirical analyzes of 4,000 eBay auctions conducted by Dell. Chapter 4 provides a statistical model where over discrete time periods, prices of online auctions follow a zero-inflated gamma distribution. Chapter 5 provides an analysis of the 44,000 bids placed in the auctions, based on bids following a gamma distribution. Both models presented in Chapters 4 and 5 are based on conditional probabilities given the price and elapsed time of an auction, and certain parameters of the competing auctions. Chapter 6 concludes the thesis with a discussion of the main results and possible extensions.

This thesis provides a discussion on some analytical and empirical models of online auctions. The objective is to provide an alternative framework for analyzing online auctions, and to characterize the distribution of intermediate prices. Chapter 1 provides a mathematical formulation of the eBay auction format and background to the data used in the empirical analysis. Chapter 2 analyzes policies for optimally disposing inventory using online auctions. It is assumed a seller has a fixed number of items to sell using a sequence of, possibly overlapping, single-item auctions. The decision the seller must make is when to start each auction. The decision involves a trade-off between a holding cost for each period an item remains unsold, and a cannibalization effect among competing auctions. Consequently the seller must trade-off the expected marginal gain for the ongoing auctions with the expected marginal cost of the unreleased items by further deferring their release. The problem is formulated as a discrete time Markov Decision Problem. Conditions are derived to ensure that the optimal release policy is a control limit policy in the current price of the ongoing auctions. Chapter 2 focuses on the two item case which has sufficient complexity to raise challenging questions. An underlying assumption in Chapter 2 is that the auction dynamics can be captured by a set of transition probabilities. Chapter 3 shows with two fixed bidding strategies how the transition probabilities can be derived for a given auction format and bidder arrival process. The two specific bidding strategies analyzed are when bidders bid: 1) a minimal increment, and 2) their true valuation. Chapters 4 and 5 provides empirical analyzes of 4,000 eBay auctions conducted by Dell. Chapter 4 provides a statistical model where over discrete time periods, prices of online auctions follow a zero-inflated gamma distribution. Chapter 5 provides an analysis of the 44,000 bids placed in the auctions, based on bids following a gamma distribution. Both models presented in Chapters 4 and 5 are based on conditional probabilities given the price and elapsed time of an auction, and certain parameters of the competing auctions. Chapter 6 concludes the thesis with a discussion of the main results and possible extensions. / Business, Sauder School of / Graduate

Partially-observable Markov decision processes (POMDPs) are especially good at modeling real-world problems because they allow for sensor and effector uncertainty. Unfortunately, such uncertainty makes solving a POMDP computationally challenging. Traditional approaches, which are based on value iteration, can be slow because they find optimal actions for every possible situation. With the help of the Fast Forward (FF) planner, FF- Replan and FF-Hindsight have shown success in quickly solving fully-observable Markov decision processes (MDPs) by solving classical planning translations of the problem. This thesis extends the concept of problem determination to POMDPs by sampling action observations (similar to how FF-Replan samples action outcomes) and guiding the construction of policy trajectories with a conformant (as opposed to classical) planning heuristic. The resultant planner is called POND-Hindsight.