Students' Abstracts

In the current scenario of information overload, the most challenging task before the computing society is to devise methods for efficient retrieval and timely delivery of relevant information in short and precise segments to the end user. The increasing availability of legal judgments in digital form creates opportunities and challenges for both the legal community and for information technology researchers. While digitized documents facilitate easy access to a large number of documents, finding all documents that are relevant to the task at hand and comprehending a vast number of them are non-trivial tasks. In this thesis we address the issues of legal judgment retrieval and of aiding in rapid comprehension of the retrieved documents. The usual practice of the legal community is that of reading the summaries (headnotes) instead of reading the entire judgments. Moreover, the legal community is also in search of an end-to-end legal information retrieval system which can give a solution for their day- to-day activities. In our thesis, a system has been proposed and tested for creating headnotes automatically from the retrieved legal judgments.

Rhetorical roles are used to represent the collection of sentences under common titles, according to their function in a narrative. Imposing a structure on a document using such roles greatly aids in comprehension. In our study, seven rhetorical roles namely identifying the case, establishing the facts of the case, arguing the case, history of the case, arguments, ratio decidendi and final decision have been identified for this purpose. We pose the problem of performing genre analysis for identifying these roles present in a judgment as one of automatic segmentation of a document. Conditional Random Fields, a discriminative graphical model has been employed in our work for text segmentation and the resulting labels are used to structure the judgments and the corresponding headnotes to aid in better comprehension.

The other major problem we address is that of retrieval of judgments relevant to the cases a legal user is currently involved in. To facilitate this we have developed a novel framework for constructing a legal knowledge base in the form of a legal ontology. Ontologies ensure efficient retrieval of resources by enabling inferences based on domain knowledge. The knowledge base developed is used to enhance the query given by the user in order to retrieve more relevant judgments. The retrieved judgments are considered for generating a final summary.

We have used term distribution model to extract important sentences from the legal judgments for the automatic summarization task. Another major issue to be handled in our study is to generate an "user-friendly" summary at the end. The rhetorical roles identified in the earlier phase have been used to improve the final summary. That is, we can significantly improve extraction-based summarization to generate coherent and concise outputs that incorporate important features of the legal judgment, namely the ratio decidendi and final decision.

The documents considered for study in this thesis are from three different sub-domains viz. rent control, income tax and sales tax related to civil court judgments. The proposed model was evaluated on a specific data collection spanning three legal sub domains. The performances of our system and other auto-summarizers available in the public domain were compared with the summary generated by a set of human subjects. It is found that, at different stages, our system-generated output is close to the outputs generated by human subjects, and it is better than the other tools considered in the study. Thus, the present work comprises almost all the aspects of finding relevant information in the document space for helping the legal communities in their information needs.

In reinforcement learning, the agent's objective is specified in terms of a scalar reward function making its accurate description crucial for success in achieving the desired behavior. In order to bypass the need to hand-engineer reward functions, Imitation learning algorithms like Generative Adversarial Imitation Learning (GAIL) estimate an expert's reward function from its demonstrations and then maximize it using RL. We observe that although GAIL is effective in matching (and often, exceeding) the expert at mean performance, high-cost trajectories, corresponding to tail-end events of catastrophic failure, are more likely to be encountered by GAIL agents than the expert. To address this issue, we develop Risk-Averse Imitation Learning (RAIL) as an alternative to GAIL in risk-sensitive applications that achieves up to 89% reduction in tail-risk at benchmark continuous control tasks of OpenAI Gym.

The sample efficiency and convergence time of an RL algorithm heavily depend on the exploration method used. While human beings use knowledge from prior experiences at related tasks while exploring a new task, most exploration algorithms for RL use the information only from the current task-environment. We develop ExTra, a framework for Transfer-guided Exploration in which we leverage a known optimal policy of a related task for efficient exploration in a new task. We demonstrate that ExTra is capable of exceeding and complementing the performance of traditional exploration algorithms.

In this work we propose a system which addresses the learning challenges explained above. The key idea here is to learn those visual properties which are common among the objects of the same class so that these properties can be later used for detecting the class. Shape, color, size, texture, etc., are examples of visual properties. A combination of these properties can represent each class and the learning is done in three phases - pattern mining phase, scoring phase and re-scoring phase. In the pattern mining phase, training image of each class is processed and the various visual properties are extracted. From these visual properties, those patterns that frequently occur are learned using frequent pattern mining. Since we are considering the frequency alone, it might happen that the operators learned will include those which covers more background pixels than the foreground ones or whose coverage is superseded by other operators. The scoring phase is used to eliminate such erroneous or extra operators. To handle discrimination and incremental addition, we have the re-scoring phase, which re- scores the operator sets learned based on how popular the operator sets are among other classes. Generally those operators which are common among many classes are considered as bad choices for discriminating the classes. Re-scoring phase tries to remove such operators by switching them with other alternatives. The system is empirically evaluated with the Caltech-101 data set and the results are presented.

We propose two supervised algorithms as viable alternatives to classical algorithms. These algorithms rely on certain probabilistic properties of usage of words in text. We empirically establish the relevance of these properties to rapid construction of high quality lexical chains through experiments we have performed. Using lexical chains formed over sense tagged documents as training data, along with a knowledge of these properties, our algorithms are shown to be capable of reliably constructing chains on a test set of documents.

Although, we believe that exploring supervised learning for chaining is a worthy investigation in its own right, we provide certain encouraging results in defence of the approach. We compare our algorithms to a classical chaining algorithm and report a 44% improvement in quality and 55 times improvement in speed. Our experiments were performed on the SemCor 3.0 dataset.

Denial of Service attacks are a major threat to the modern electronic society. Carefully crafted attacks of large magnitude, better referred to as Distributed Denial of Service attacks (DDoS) have the ability to cause havoc at the highest level, national information infrastructure. The ease at which such attacks can be performed today is startling given the number of free online tools available in the open. An ideal situation would be to differentiate between good and bad packets as generally attempted and accomplished in the case of intrusion attempts, which in the case of DoS attacks is extremely hard as only the intent differs between a genuine user and an attacker.

There are multiple perspectives of dealing with the DoS attack problem, in order to mitigate, detect and cope with detected attack. Techniques dealing with each of these aspects can be integrated to make a fool-proof system. An important such perspective in terms of detecting DoS attacks is to view the problem as that of a classification problem on network state (and not on individual packets or other units) by modelling normal and attack traffic and classifying the current state of the network as good or bad, thereby detecting attacks when they happen. Classical machine learning algorithms are used to solve the problem.

In this work, the approach to a carefully engineered, practically realisable system to detect DoS attacks based on a Nai�ve Bayesian classifier is described. The system is designed to be near the target. The focus of the system is on two transport layer protocols - TCP and UDP, both of which work on a common framework of mechanisms, although with different input parameters.

For the TCP protocol, TCP flags are taken as the feature, and the probability space is engineered taking into account hardware implementability and operability at line speeds. Simple independence assumptions are made inside a window of packets, and the probability of a window is determined as a function of the probabilities of flag combinations observed inside the window. Threshold probability is determined by cross validation - a technique commonly used in data mining. For the UDP protocol, the feature is the Windows Arrival Time (WAT), the time taken for a window of packets to arrive at the mitigation device. Techniques similar to TCP are used.

Experiments are carried out with both tagged and untagged datasets, and the results are found to be promising. In order to assert the efficiency and usefulness of our system, the system was compared with a one-class SVM classifier, and found to be more suitable for hardware implementation.

• Linked Data Classification: In general, all the machine learning paradigms assume the data points to be independent and identically distributed (i.i.d). But many real-world datasets such as webpages, images and protein interaction networks possess additional link information which provides local label smoothness. For example, in webpage classification, links between webpages convey that there is a strong correlation between labels of the linked pages. This can be exploited to provide regularization and thereby improve the performance. Collective classification is one of the popular approaches that can handle this type of network data. It combines traditional machine learning and link based classification in an iterative procedure. This involves two important steps: 1) collective learning - training the base classifier on the appended content and link information with the given (partially) labeled network data; and 2) collective inference - applying the trained base classifier on the partially labeled network data and labeling it completely. Most of the collective classification frameworks assume that sufficient labeled data is available for training the base classifier. The trained base classifier is applied on the test data iteratively to perform collective inference. But, there has been little attention paid towards collective learning on partially labeled network data. We propose a multi-view learning based algorithm which utilizes both content and link views effectively to learn from the unlabeled data also. We empirically evaluate the effectiveness of the proposed framework by showing that it performs better than traditional single view approaches on sentiment analysis and standard linked datasets such as Cora, Citeseer and WebKB. We also performed sentiment analysis on automobile reviews.
• Similar Protein Structures Retrieval: With the rapid expansion of protein structure databases, the task of efficiently retrieving structures similar to a given protein has gained importance. It involves two major issues: (i) an effective protein structure representation that captures inherent relationship between fragments and facilitates efficient comparison between structures, (ii) an effective framework to accommodate different retrieval requirements. Recently, researchers proposed a vector space model of proteins using bag of fragments representation (FragBag), which corresponds to a basic information retrieval model. In this work, first, we propose an improved representation of protein structures using Latent Dirichlet Allocation (LDA) topic model. Second, we handle the most important requirement which is to retrieve proteins, whether they are close or intermediate or remote homologs. Close, remote and intermediate homologs are defined based on Structural Alignment Score (SAS). The SAS thresholds typically are 2, 3.5 and 5 for close, intermediate and remote homologs respectively. In order to meet diverse objectives, we propose a multi-view based framework that combines multiple representations and retrieval techniques. We experimentally show that the proposed multi-view based retrieval framework performs better than state-of-the-art filter and match techniques across different retrieval requirements. The experiments are performed on FragBag dataset, which contains 2,930 sequence non-redundant structures selected from CATH version 2.4.

Markov Logic Networks belong to the class of Statistical Relational Learning (SRL) methods that combine the expressiveness of first-order logic and the ability of probability theory to handle uncertainty. MLNs extend Markov networks to a relational setting by expressing the knowledge as a set of weighted formulas. We propose a layered MLN design which performs stage-wise inference to allow for reasoning at multiple levels and at varying levels of uncertainty. Given that the information is incomplete, active vision is a mechanism for focused gathering of additional information. Our framework integrates active vision with the layered MLN model to gather missing evidence, facilitating reliable and tractable inference. Inspired by the ideas of active vision, in the event of missing evidence, our framework restricts the selective visual processing to specific regions of the input image and further inference is carried out incorporating the new evidence.

We present a cognitively motivated, complete end-to-end system for object categorization in a SRL framework. We use three different datasets for experimental evaluation: synthetic images generated using OpenCV library, images obtained from the iCub humanoid simulator and real images taken from Microsoft's Kinect Xbox (R). The system is evaluated with different levels of incompleteness and noise on these datasets and empirically prove its applicability to detect objects of complex structures.

Robots have captivated human imagination for a long time. Numerous science fictions have promised that the era of robots is beckoning and the day androids walk shoulder to shoulder with us is not too far away. If this were to happen, the intelligent systems that would populate our environment will have to adapt and learn fast, possibly from humans too. For such systems, human teachers present a narrow but critical learning environment. Even between humans, the interactive teacher-student relationship is known to be effective. Endowing robots with human-like learning capabilities would facilitate a similar human- machine interaction, resulting in effective utilization of human knowledge by the robot. We model a subset of these interactions as instructions and propose a framework that enables humans to instruct robots and robots to exploit these supervisory inputs. In all of our experiments, the systems are based on Reinforcement Learning (RL).

In RL, rewards have been considered the most important feedback in understanding environments. However, recently there have been interesting forays into other modes such as sporadic human instructions. We utilize these instructions to identify structural regularities in the environment that can aid in taking behavioural decisions in unfamiliar situations. An important aspect of working with instructions is their proper interpretation. Our approach accommodates multiple interpretations of instructions and provides a handle to choose the best. In this regard, we have tested our approach on several domains and implemented it on a real robotic system.

Any activity aimed at disrupting a service or making a resource unavailable or gaining unauthorized access can be termed as an intrusion. Examples include buffer over-flow attacks, flooding attacks, system break-ins, etc. Intrusion Detection Systems (IDS) play a key role in detecting such malicious activities and enable administrators in securing network systems. Two key criteria should be met by an IDS for it to be effective: (a) ability to detect unknown attack types (b) having very less misclassification rate.

Over the last decade, using Machine Learning (ML) techniques to address the problem of detecting network intrusions has become prevalent. The ability to detect novel intrusions sets apart ML based systems from standard signature based intrusion detection methods. In this work, the problem of detecting network intrusions is posed as a classification problem. The classifier built should be able to separate good/legitimate traffic from bad/anomalous traffic. Machine Learning (ML) based classfiers are used to build our IDS. It profiles clean traffic traces and uses the model built to classify unseen traffic.

In this work, we describe a two stage network intrusion detection system (NIDS) that can operate at high packet rates. In the first stage, which is in-line with the network, we use Naïve Bayesian based probabilistic classifier to detect potential anomalies in the trafic. In the second stage, a cascaded Hidden Markov Model (HMM) is used to pin down the potential IP address of misbehaving connections. Various design choices that were made to make this system practical and the difficulties faced while integrating the system with existing models are also described. Experiments were conducted to evaluate the performance and to validate the proposed model. We show that this system achieves good performance empirically.

Communication has become a lot easier with the advent of easy and cheap means of reaching people across the globe. This has allowed the development of large networked communities and, with the technology available to track them, has opened up the study of social networks at unprecedented scales. This has necessitated the scaling up of various network analysis algorithms that have been proposed earlier in the literature. While some algorithms can be readily adapted to large networks, in many cases the adaptation is not trivial.

Real-world networks typically exhibit non-uniform edge densities with there being a higher concentration of edges within modules or communities. Various scoring functions have been proposed to quantify the quality of such communities. The popu- lar scoring functions suffer from certain limitations. This thesis identifies the necessary features that a scoring function should incorporate in order to characterize good community structure and propose a new scoring function, CEIL (Community detection using External and Internal scores in Large networks), which conforms closely with the characterization. It also demonstrates experimentally the superiority of CEIL score over the existing scoring functions. Modularity, a very popular scoring function, exhibits a resolution limit, i.e., one cannot find communities that are much smaller in size compared to the size of the network. In many real world networks, community size does not grow in proportion to the network size. This implies that resolution limit is a serious problem in large networks. Still modularity is very popular since it offers many advantages such as fast algorithms for maximizing the score, and non-trivial community structures corresponding to the maxima. This thesis shows analytically that the CEIL score does not suffer from resolution limit. It also modifies the Louvain method, one of the fastest greedy algorithms for maximizing modularity, to maximize the CEIL score. The modified algorithm, known as CEIL algorithm, gives the expected communities in synthetic networks as opposed to maximizing modularity. The community labels given by CEIL algorithm matches closely with the ground-truth community labels in real world networks. It is on par with Louvain method in computation time and hence scales well to large networks.

This thesis also explores the scaling up of a class of node centrality algorithms based on cooperative game theory which were proposed earlier as efficient alternatives to traditional measure of information diffusion centrality. It presents the distributed versions of these algorithms in a Map-Reduce framework, currently the most popular distributed computing paradigm. The scaling behavior of the distributed version of algorithms on large synthetic networks is demonstrated empirically thereby establishing the utility of these methods in settings such as online social networks.

In social network analysis, the fundamental idea behind the notion of position is to discover actors who have similar structural signatures. Positional analysis of social networks involves partitioning the actors into disjoint sets using a notion of equivalence which captures the structure of relationships among actors. Classical approaches to Positional Analysis, such as Regular equivalence and Equitable Partitions, are too strict in grouping actors and often lead to trivial partitioning of actors in real world networks. An epsilon-Equitable Partition (eEP) of a graph is an useful relaxation to the notion of structural equivalence which results in meaningful partitioning of actors. All these methods assume a single role per actor, actors in real world tend to perform multiple roles. For example, a Professor can possibly be in a role of "Advisor" to his PhD students, but in a role of "Colleague" to other Professors in his department.

In this thesis we propose epsilon-equitable partitions based approaches to perform scalable positional analysis and to discover positions performing multiple roles. First, we propose and implement a new scalable distributed algorithm based on MapReduce methodology to find eEP of a graph. Empirical studies on random power-law graphs show that our algorithm is highly scalable for sparse graphs, thereby giving us the ability to study positional analysis on very large scale networks.

Second, we propose a new notion of equivalence for performing positional analysis of networks using multiple epsilon-equitable partitions. These multiple partitions give us a better bound on identifying equivalent actor "positions" performing multiple "roles".

Evaluation of our methods on multi-role ground-truth networks and time evolving snapshots of real world social graphs show the importance of epsilon equitable partitions for discovering positions performing multiple roles and in studying the evolution of actors and their ties.

Classical Machine Learning (ML) algorithms learn to do a specific task, say classification by using the available training data and classify the test data which is unknown during the training. However, all these algorithms assume that the data is represented using a set of features, which are mostly hand-crafted by human experts. Learning useful features or representations from the raw data, also known as Representation Learning is one of the hardest problems in Machine Learning. Deep Learning is an emerging field in Machine Learning which solves the problem of representation learning using Deep Neural Networks (DNNs). These representations learned using Deep Neural Networks, when coupled with simple classification algorithms, perform significantly better than the complex state-of-the-art procedures in text, image and speech data.

Common Representation Learning (CRL), wherein different descriptions (or views) of the data are embedded in a common subspace, is receiving a lot of attention recently. Two popular paradigms in CRL world are Canonical Correlation Analysis (CCA) based approaches and Autoencoder (AE) based approaches. CCA based approaches learn a joint representation by maximizing correlation of the views when projected on the common subspace. AE based methods learn a common representation by minimizing the error of reconstructing the two views. Each of these approaches has its own advantages and disadvantages. For example, though CCA based approaches outperform AE based approaches for the task of transfer learning, they are not as scalable as the latter.

In this thesis, we propose Correlational Neural Networks (CorrNet), a class of neural networks that can learn common representation for two different views. CorrNet is an AE based approach, that explicitly maximizes correlation among the views when projected on the common subspace. The model can be efficiently trained with batch gradient descent and is thus scalable to big data. Apart from learning common representation for different views, the model also learns to predict the features in one view given the features in the other view, which has several interesting applications. CorrNet, unlike CCA, can be easily extended to more than two views. Experiments show that CorrNet outperforms CCA in learning common representation. Thus scalability is gained without compromising performance. The CorrNets come with another advantage, that is, it can make use of single view data when there are less parallel data and this is not possible in CCA.

CorrNet has been successfully applied in Natural Language Processing (NLP) to several cross lingual tasks where a learner has to learn from one language and perform in a different language. In the task of Cross Language Document Classification (CLDC), CorrNet based bilingual word representation learning algorithm performs significantly better than the current state of the art procedures and a strong Machine Translation baseline. The model is also applied in Transliteration Mining. It has been tested with several language pairs and works well even if the languages differ in scripts, since the model itself is not language dependent.

CorrNet can be considered as a variant of auto-encoder to handle multi-view data. In this thesis, we also propose ways to make the CorrNet deep. One of the deep versions of the CorrNet performs much better than several strong baselines in the task of Cross Language Sentiment Analysis (CLSA). All the mentioned studies leads us to believe that CorrNet is a promising tool from common representation learning.

Social networks have become an effective means of communication among people. Recently, there is a trend to analyze these social networks to infer the dynamics of human interaction. A fundamental problem in behavioral analysis of human interactions is to understand how communications unfold. In this thesis, we propose and solve the problem of mining Communication motifs from dynamic interaction networks. Simply stated, a communication motif is a recurring subgraph that has a similar sequence of information flow. Communication motifs provide a powerful mechanism to capture the dynamics of human interactions.

Building intelligent robots has been one of the motivating problems in Artificial Intelligence research. Choosing what actions to perform is a fundamental problem every robot must solve. The aptness of the actions depends on the robot's understanding of its environment and the dynamics involved. This understanding is an ever-changing model based on the robot's observations and experiences. In this thesis, we propose a robot-learning architecture and discuss two key modules - a continuous space path planning algorithm and an activity recognition framework.

Path planning in continuous spaces is a challenging problem for which a variety of solutions have been proposed. The performance of sampling based path planning techniques relies on identifying a good approximation to the cost-to-go distance metric, in the case of systems with complex dynamics. We propose a technique that uses reinforcement learning to learn this distance metric on the fly from samples and combine it with existing sampling based planners to produce near optimal solutions. The resulting algorithm - Policy Iteration on Rapdily exploring Random Trees (RRTPI) can solve problems with complex dynamics in a sample-efficient manner while preserving asymptotic guarantees. We provide experimental evaluation of this technique on domains with under-actuated and underpowered dynamics such as the mountain car domain, the acrobot domain and a variant of the octopus arm domain.

Human activity recognition is a key component in enabling social robots to naturally interact with humans. While humans can easily distinguish whether an activity corresponds to a form of communication or an act of daily living, robots are yet not that insightful. This thesis addresses the problem of enabling a social robot to understand an activity as well as classify it as an action corresponding to a human instruction or an act of daily living. We address this problem by presenting a simple yet effective approach of modeling pose trajectories in terms of directions taken by skeletal joints over the duration of an activity. Specifically, we propose a novel activity descriptor: Histogram of direction vectors (HODV). The descriptor is computationally efficient, scale and speed invariant and provides state of the art classification accuracies using off the shelf classification algorithms on multiple datasets such as the Cornell Activity Dataset (CAD-60), UT-Kinect Dataset as well as on our novel RGBD dataset.

In recent years, Recommender Systems (RSs) have become ubiquitous. Factorization models are a common approach to solve RSs problems, due to their simplicity, prediction quality and scalability. The idea behind such models is that preferences of a user are determined by a small number of unobserved latent factors. One of the most well studied factorization model is matrix factorization using the Frobenius norm as the loss function. In more challenging prediction scenarios where additional "side-information" is available and/or features capturing higher order may be needed, new challenges due to feature engineering needs arise. The side-information may include user specific features such as age, gender, demographics, and network information and item specific information such as product descriptions. While interactions are typically desired in such scenarios, the number of such features grows very quickly. This dilemma is cleverly addressed by the Factorization Machine (FM), which combines high prediction quality of factorization models with the flexibility of feature engineering. Interestingly, the framework of FM subsumes many successful factorization models like matrix factorization, SVD++, TimeSVD++, Pairwise Interaction Tensor Factorization (PITF), and factorized personalized Markov chains (FPMC). Also, due to the availability of large data, several sophisticated probabilistic factorization models have been developed. However, in spite of having a vast literature on factorization models, several problems exist with different factorization model algorithms.

In this thesis, we take a probabilistic approach to develop several factorization models. We adopt a fully Bayesian treatment of these models and develop scalable approximate inference algorithms for them.

Bayesian Probabilistic Matrix Factorization (BPMF), which is a Markov chain Monte Carlo (MCMC) based Gibbs sampling inference algorithm for matrix factorization, pro- vides state-of-the-art performance. BPMF uses multivariate Gaussian prior on latent factor vector which leads to cubic time complexity with respect to the dimension of latent space. To avoid this cubic time complexity, we develop the Scalable Bayesian Matrix Factorization (SBMF) which considers independent univariate Gaussian prior over latent factors. SBMF, which is a MCMC based Gibbs sampling inference algorithm for matrix factorization, has linear time complexity with respect to the dimension of latent space and linear space complexity with respect to the number of non-zero observations.

We then develop the Variational Bayesian Factorization Machine (VBFM) which is a batch scalable variational Bayesian inference algorithm for FM. VBFM converges faster than the existing state-of-the-art MCMC based inference algorithm for FM while providing similar performance. Additionally for large scale learning, we develop the Online Variational Bayesian Factorization Machine (OVBFM) which utilizes stochastic gradient descent to optimize the lower bound in variational approximation. OVBFM outperforms existing online algorithms for FM as validated by extensive experiments performed on numerous large-scale real world data.

Finally, the existing inference algorithm for FM assumes that the data is generated from a Gaussian distribution which may not be the best assumption for count data such as integer-valued ratings. Also, to get the best performance, one needs to cross-validate over the number of latent factors used for modeling the pairwise interaction in FM, a process that is computationally intensive. To overcome these problems, we develop the Nonparametric Poisson Factorization Machine (NPFM), which models count data using the Poisson distribution, provides both modeling and computational advantages for sparse data. The ideal number of latent factors is estimated from the data itself. We also consider a special case of NPFM, the Parametric Poisson Factorization Machine (PPFM), that considers a fixed number of latent factors. Both PPFM and NPFM have linear time and space com- plexity with respect to the number of non-zero observations. Using extensive experiments, we show that our methods outperform two strong baseline methods by large margins.

Reinforcement Learning (RL) is a collection of learning approaches that solve for a behavior of an agent in a world maximizing some notion of payoff. Under certain circumstances the agent's world, described by a set of parameters, is essential to be learnt for it to discover an optimal behavior. This paradigm of problems is studied under the broad topic of model-based RL, and the class of algorithms that help an agent in learning the model parameters are known as model learning algorithms. In this thesis, we discuss exploration strategies in model-based RL from two different perspectives - asymptotic agent, where early convergence to an optimal solution is desirable but not a necessity, and finite-episode agent, which has a constraint on the number of episodes to converge to an optimal behavior.

The first part of this thesis proposes a novel uncertainty based exploration strategy, Thompson Sampling with Exploration Bonus (TSEB), for the asymptotic agent case. This work draws insights from Thompson Sampling, a Bayesian approach to modelbased RL, and the homomorphism literature in RL. The proposed algorithm helps the agent learn close to true model parameters of the world with lesser sample complexity than the existing model learning algorithms. TSEB algorithm trades off the proposed exploration bonus with the sampled reward estimate in Thompson Sampling algorithm. This strategy, with the elegance of Bayesian approach, provides a better way to learn model parameters and is validated theoretically and empirically in this thesis.

Despite having sound strategies for the asymptotic case, the finite-episode case in RL has been seldom looked into. The other part of this thesis studies the exploration strategies of finite-episode agents and proposes a novel framework, Structuring FiniteEpisode Exploration (SFEE) in Markov Decision Processes, that adapts an asymptotic exploration strategy for finite-episode setting. This work justifies the need for such a framework by showing that the asymptotic exploration strategies don't suit the finite-episode setting which can be because of them not being conscious of the agent's lifetime. Aiming to make good use of the sound strategies of asymptotic learning algorithms, the proposed framework uses the policy of an asymptotic algorithm plugged into the framework for a certain number of episodes and then appropriately switches to a greedy policy. Further, this thesis shows, under some mild assumptions, that this is indeed the optimal way to explore in a finite-episode setting using that exploration algorithm. The framework also enables exporting theoretical guarantees from the plugged asymptotic algorithm to the proposed framework.

This thesis studies the following topics in the area of Reinforcement Learning: classic Multi-armed bandits in stationary distribution with the goal of cumulative regret minimization using variance estimates and Thresholding bandits in pure exploration fixed-budget setting with the goal of instantaneous regret minimization also using variance estimates. The common underlying theme is the study of bandit theory and its application in various types of environments.

In the first part of the thesis, we study the classic multi-armed bandit problem with a stationary distribution, one of the first settings studied by the bandit community and which successively gave rise to several new directions in bandit theory. We propose a novel algorithm in this setting and compare both theoretically and empirically its performance against the available algorithms. Our proposed algorithm termed as Efficient-UCB-Variance (EUCBV) is the first arm-elimination algorithm which uses variance estimation to eliminate arms as well as achieve an order optimal regret bound. Empirically, we show that EUCBV outperforms most of the state-of-the-art algorithms in the considered environments.

In the next part, we study a specific type of stochastic multi-armed bandit setup called the thresholding bandit problem and discuss its usage, available state-of-the-art algorithms on this setting and our solution to this problem. We propose the Augmented-UCB (AugUCB) algorithm which again uses variance and mean estimation along with arm elimination technique to conduct exploration. We give theoretical guarantees on the expected loss of our algorithm and also analyze its performance against state-of-the-art algorithms in numerical simulations in multiple synthetic environments.

In the field of mobile robotics, robot tasks usually involve navigation in a known or unknown environment, for which the robot needs a map of that environment and also needs to know its position within the operating area. Although there are techniques like SLAM (Simultaneous Localization and Mapping) where a map is constructed and/or updated while simultaneously localizing the robot, they do need a map for localizing. So, in any case, having a map at hand is advantageous.

Traditional map construction methods depend extensively on costly sensors. For indoor applications, the robot has to wander around the world numerous timesto catch as much data as possible to construct a map, mostly supervised by human. Vision based navigation systems are hence gaining popularity because of being cheap and easy to handle. While map building is easier using multiple vision systems or using multiple images, map construction from single image is definitely a harder problem, although its applications are immense.

In the domain of robotics, the idea of constructing maps from a single image taken from monocular cameras might solve several complex issues related to path planning and navigation. Owing to its diverse applications, the current research focus is on developing methods which would utilize the properties of the images. One such property being considered is Vanishing points (VPs). Existing methods on single camera vision systems depend either on multiple images or on prior information to be fed to the system. The focus of the research presented in this thesis is to develop geometrical methods that will take advantage of VPs for constructing scaled 2D free- space maps and 3D models from a single image, the image being either in two-point perspective (2PP) or three-point perspective (3PP).

Given an image with one or more objects in it, the proposed approach is to bring all the objects to a common ground depth w.r.t. the camera view point. This will ensure that all the objects' projections are to a common scale and thus a scaled map can be constructed. The principal contribution of this thesis is the concept of side view geometry of an image, which is first of its kind. All the mathematical derivations have been done using the proposed side view geometry. A systematic method has been developed, which has been proved as a generalized approach for both 2PP and 3PP cases. A generalized algorithm has been developed, coded, tested with some case studies, and the results are compared with the ground truths. The effectiveness of the proposed method is established through the results and the error plots.

A new methodology for path planning of mobile robots in known environments with static obstacles is also proposed in this thesis. A new concept of multi-bug system will be introduced. Multi Bug Path Planning (MBPP) works by assuming a virtual bug that move towards the goal from the start state. If in case it meets an obstacle, then that bug generates a new bug. The two bugs now move along walls of the obstacle in either direction until specific conditions are met. Bug generation continues whenever any of the current bugs hit a new obstacle, until target is reached by all live bugs. MBPP thus evaluates best possible paths for a given environment and chooses the best route that is supposed to be optimal. Experimentally, it will be shown that MBPP finds paths that are shorter and comparable with post-smoothed A* in lesser runtimes. Proposed work on MBPP is an attempt to combine the features of offline and online methods so that the same algorithm could be used for both cases. Current work on MBPP demonstrates the offline case with static obstacles in a priori known environment.