Analysis and control of stochastic systems

Markov decision theory

J. N. Tsitsiklis, "NP-Hardness of Checking the Unichain Condition in Average Cost MDPs," Operations Research Letters, Vol. 35, No. 3, May 2007, pp. 319-323.

S. Mannor and J. N. Tsitsiklis, "On the Empirical State-Action Frequencies in Markov Decision Processes Under General Policies", Mathematics of Operations Research, Vol. 30, No. 3, August 2005, pp. 545-561.

D.P. Bertsekas and J.N. Tsitsiklis, "An Analysis of Stochastic Shortest Path Problems", Mathematics of Operations Research, Vol. 16, No. 3, August 1991, pp. 580-595.

G. H. Polychronopoulos and J. N. Tsitsiklis, "Stochastic Shortest Path Problems with Recourse", Networks, Vol. 27, No. 2, 1996, pp. 133-143.

H.N. Psaraftis and J.N. Tsitsiklis, "Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs", Operations Research, Vol. 41, 1, 1993, pp. 91-101.

C.-S. Chow and J.N. Tsitsiklis, "An Optimal One-Way Multigrid Algorithm for Discrete-Time Stochastic Control", IEEE Transactions on Automatic Control, Vol. AC-36, No. 8, 1991, pp. 898-914.

C.H. Papadimitriou and J.N. Tsitsiklis, "The Complexity of Markov Decision Processses", Mathematics of Operations Research, Vol. 12, No. 3, 1987, pp. 441-450.

See also Neuro-Dynamic Programming

Stochastic approximation

V. R. Konda and J. N. Tsitsiklis, "Linear Stochastic Approximation Driven by Slowly Varying Markov Chains", Systems and Control Letters, Vol. 50, No. 2, 2003, pp. 95-102.

V. R. Konda and J. N. Tsitsiklis, "Convergence Rate of Linear Two-Time Scale Stochastic Approximation", Annals of Applied Probability, Vol. 14, No. 2, 2004,

D. P. Bertsekas and J. N. Tsitsiklis, "Gradient Convergence in Gradient Methods with Errors," SIAM Journal in Optimization, Vol. 10, No. 3, 2000, pp. 627-642.

J. N. Tsitsiklis, "Asynchronous Stochastic Approximation and Q-learning", Machine Learning, 16, 1994, pp. 185-

J. N. Tsitsiklis, D. P. Bertsekas and M. Athans, "Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms," IEEE Transactions on Automatic Control, Vol. 31, No. 9, 1986, pp. 803-812.

Multi-armed bandit and search problems

S. Das and J. N. Tsitsiklis, "When is it Important to Know You've Been Rejected? A Search Problem with Probabilistic Appearance of Offers," submitted, May 2006.

J. Sethuraman and J. N. Tsitsiklis, "Stochastic Search in a Forest Revisited," Mathematics of Operations Research, Vol. 32, No. 3, August 2007, pp. 589-593.

S. Mannor and J. N. Tsitsiklis, "The Sample Complexity of Exploration in the Multi-Armed Bandit Problem," Journal of Machine Learning Research, Vol. 5, June 2004, pp. 623-648.

D. Bertsimas, I. Paschalidis and J. N. Tsitsiklis, "Branching Bandits and Klimov's Problem: Achievable Region and Side Constraints" , IEEE Transactions on Automatic Control, Vol. 40, No. 12, December 1995, pp. 2063-2075.

J. N. Tsitsiklis, "A Short Proof of the Gittins Index Theorem", Annals of Applied Probability, Vol. 4, No. 1, 1994, pp. 194-199.

J.N. Tsitsiklis, "A Lemma on the Multi-Armed Bandit Problem", IEEE Transactions on Automatic Control, Vol. 31, No. 6, 1986, pp. 576-577.

Stochastic Scheduling and Inventory Control

D. Shah and J. N. Tsitsiklis, "Bin Packing with Queues," Journal of Applied Probability, in press.

N. Sabbaghi, Y. Sheffi, and J. N. Tsitsiklis, "Coordination capability of linear wholesale price contracts ", technical report LIDS-P-2749, Laboratory for Information and Decision Systems, MIT, February 2007.

A. Muharremoglu and J. N. Tsitsiklis, "Dynamic Leadtime Management in Supply Chains," unpublished manuscript, June 2003.

A. Muharremoglu and J. N. Tsitsiklis, "A Single-Unit Decomposition Approach to Multi-Echelon Inventory Systems", July 2001 (revised September 2007); Operations Research, in press.

B. Van Roy, D. P. Bertsekas, Y. Lee, and J. N. Tsitsiklis, "A Neuro-Dynamic Programming Approach to Retailer Inventory Management", November 1996. Short version in Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, California, December 1997, pp. 4052-4057.

C.H. Papadimitriou and J.N. Tsitsiklis, "Stochastic Scheduling with In-Tree Precedence Constraints", SIAM Journal on Computing, Vol. 16, No. 1, 1987, pp. 1-6.

J.N. Tsitsiklis, "Periodic Review Inventory Systems with Continuous Demand and Discrete Order Sizes", Management Science, Vol. 30, No. 10, 1984, pp. 1250-1254.

J.N. Tsitsiklis, "Convexity and Characterization of Optimal Policies in a Dynamic Routing Problem", Journal of Optimization Theory and Applications, Vol. 44, No. 1, 1984, pp. 105-136.

G.D. Stamoulis and J.N. Tsitsiklis, "Optimal Distributed Policies for Choosing Among Multiple Servers", Proceedings of the 30th IEEE Conference on Decision and Control, Brighton, England, December 1991, pp. 815-820.

Simulated annealing

J.N. Tsitsiklis, "Markov Chains with Rare Transitions and Simulated Annealing", Mathematics of Operations Research, Vol. 14, No. 1, 1989, pp. 70-90.

J.N. Tsitsiklis, "A Survey of Large Time Asymptotics of Simulated Annealing Algorithms", in Stochastic Differential Systems, Stochastic Control Theory, and Applications, W. Fleming and P. L. Lions, (Eds.), Springer-Verlag, New York, 1988, pp. 583-599.

D. Bertsimas and J. N. Tsitsiklis, "Simulated Annealing", Statistical Science, Vol. 8, No. 1, 1993, pp. 10-15.

Computation with noisy gates

N. Pippenger, G.D. Stamoulis, and J.N. Tsitsiklis, "On a Lower Bound for the Redundancy of Reliable Networks with Noisy Gates", IEEE Transactions on Information Theory, Vol. IT-37, May 1991, pp. 639-643.