Identifying sequences of actions required to complete tasks, based on data of completed tasks
What is the best way to solve this?
Based on my knowledge of linear regression and classification, I believe that both are not the right approach to solve the task at hand.

Not sure about the best way, but one indeed can formulate this kind of problem as a classification problem. I assume that additionally to the data included in your sample dataset you also have information about the environment for all 1,000 observations.
For example, one can reshape the dataset as follows.
Underlying data (I've inserted env as a placeholder for the information about environment, you might have several variables describing the environment):
|task |env |action1 |action2 |action3 |action4 |action5 |
|:----|:---|:-------|:-------|:-------|:-------|:-------|
|T1   |E1  |A5      |A1      |A3      |END     |NA      |
|T2   |E2  |A7      |A12     |A4      |A1      |END     |
|T1   |E3  |A5      |A3      |A13     |END     |NA      |

Transformed dataset that can be passed to the classifier
|task |env | num_action|prev_action |action |
|:----|:---|----------:|:-----------|:------|
|T1   |E1  |          1|START       |A5     |
|T2   |E2  |          1|START       |A7     |
|T1   |E3  |          1|START       |A5     |
|T1   |E1  |          2|A5          |A1     |
|T2   |E2  |          2|A7          |A12    |
|T1   |E3  |          2|A5          |A3     |
|T1   |E1  |          3|A1          |A3     |
|T2   |E2  |          3|A12         |A4     |
|T1   |E3  |          3|A3          |A13    |
|T1   |E1  |          4|A3          |END    |
|T2   |E2  |          4|A4          |A1     |
|T1   |E3  |          4|A13         |END    |
|T2   |E2  |          5|A1          |END    |

Then one can apply any multiclass classification (e.g. multinomial logistic regression) and try to predict the column action using the first four columns as predictors.